# 22. Generate Parentheses

## 10 Jan 22. Generate Parentheses

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`

https://segmentfault.com/a/1190000006121957

Find a path to success 有没有解
Find all paths to success 求所有解

Find the best path to success 求最优解

class Solution(object):
def generateParenthesis(self, n):
“””
:type n: int
:rtype: List[str]
“””
res = []
self.dfs(res, n, n, ”)
return res

def dfs(self, res, left, right, path):
if left == 0 and right == 0:
res.append(path)
return
if left > 0:
self.dfs(res, left – 1, right, path + ‘(‘)
if left < right:
self.dfs(res, left, right – 1, path + ‘)’)

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
results = []
def dfs(results, left, right, path):
print(‘———————-‘)
print(left)
print(right)
print(path)
if left == 0 and right == 0:
results.append(path)
return
if left > 0:
dfs(results, left – 1, right, path + ‘(‘)
if left < right:
dfs(results, left, right – 1, path + ‘)’)

dfs(results, n, n, ”)
return results