1 题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
2 解析
（1）方法一：暴力求解
为了生成所有序列，我们可以使用递归。长度为 nn 的序列就是在长度为 n−1 的序列前加一个 (’ 或 ‘)’。
为了检查序列是否有效，我们遍历这个序列，并使用一个变量balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时balance 的值不为零，那么该序列就是无效的，否则它是有效的。
（2）方法二：回溯方法
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
3 Python实现
（1）方法一
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
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
（2）方法二
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(A,left,right):
if len(A)==2*n:
ans.append(''.join(A))
return
if left <n:
A.append('(')
backtrack(A,left+1,right)
A.pop()
if right<left:
A.append(')')
backtrack(A, left, right+1)
A.pop()
ans = []
backtrack([],0,0)
return ans
