<div>
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
<pre>Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] </pre>
Example 2:
<pre>Input: n = 1 Output: ["()"] </pre>
Constraints:
1 <= n <= 8
</div>
题目大意：
产生n对括号的所有可能
算法思路：
DFS填位法，运用括号定律1： 左括号数 >= 右括号数，也就是左括号剩余数 < 右括号剩余数
注意事项：
- 复杂度的计算
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def generateParenthesis(self, n: int) -> List[str]:
res = []
self.dfs(n, n, '', res)
return res
def dfs(self, left_paren_left, right_paren_left, path, res):
if left_paren_left == 0 and right_paren_left == 0:
res.append(path)
return
if left_paren_left > 0:
path += '('
self.dfs(left_paren_left - 1, right_paren_left, path, res)
path = path[:-1]
if right_paren_left > 0 and left_paren_left < right_paren_left:
path += ')'
self.dfs(left_paren_left, right_paren_left - 1, path, res)
path = path[:-1]
算法分析：
n个括号，有2n位，时间复杂度为Catalan数O[C(n,2n)/n+1]，空间复杂度O(n)
