Description
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8
Solution
Python3
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(opened, closed, curr):
if opened == closed == n:
res.append(curr)
return
if closed < opened:
backtrack(opened, closed + 1, curr + ")")
if opened < n:
backtrack(opened + 1, closed, curr + "(")
backtrack(0, 0, "")
return res