class Solution:
def generateParenthesis(self, n: int) -> List[str]:
path = []
res = []
self.dfs(0, 0, n, path, res)
return res
def dfs(self, left: int, right:int, n: int, path: List, res: List):
if len(path) == 2 * n:
res.append(''.join(path))
return
if left < n: # 左右条件是关键, 普通回溯模版里可能是通过for循环逐个加，但括号只分别考虑左和右
path.append('(')
self.dfs(left + 1, right, n , path, res)
path.pop() # 这里，为什么在加入右上面就pop. 类似把一般回溯for循环的多个条件分开写
if right < left:
path.append(')')
self.dfs(left, right + 1, n , path, res)
path.pop()
时间复杂度：O(4^n / sqrt(n))
空间复杂度：O(n)
def generateParenthesis(self, n: int) -> List[str]:
def dfs(left, right, s):
if len(s) == n * 2:
res.append(s)
return
if left < n:
dfs(left + 1, right, s + '(')
if right < left:
dfs(left, right + 1, s + ')')
res = []
dfs(0, 0, '')
return res