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
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def gen(left: int, right: int, cur: str) -> None:
if left == 0 and right == 0:
res.append(cur)
return
if left > 0:
gen(left-1, right, cur + '(')
if right > 0 and left < right:
gen(left, right-1, cur + ')')
gen(n, n, '')
return res
|