题目 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
暴力
def generateParenthesis(self
, n
):
def generate(A
= []):
if len(A
) == 2*n
:
if valid
(A
):
ans
.append
("".join
(A
))
else:
A
.append
('(')
generate
(A
)
A
.pop
()
A
.append
(')')
generate
(A
)
A
.pop
()
def valid(A
):
bal
= 0
for c
in A
:
if c
== '(': bal
+= 1
else: bal
-= 1
if bal
< 0: return False
return bal
== 0
ans
= []
generate
()
return ans
回溯
def generateParenthesis(self
, n
: int) -> List
[str]:
ans
= []
def backtrack(S
= '', left
= 0, right
= 0):
if len(S
) == 2 * n
:
ans
.append
(S
)
return
if left
< n
:
backtrack
(S
+'(', left
+1, right
)
if right
< left
:
backtrack
(S
+')', left
, right
+1)
backtrack
()
return ans
