题目
- 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
题解：回溯+剪枝
- 首先翻译一下题目：现在有2n个位置，每个位置可以放'('或者')'，组成的所有括号组合中，有多少个是合法的？并保存输出。
- 思路：先把所有的括号组合穷举出来，在筛选合法的即可
- 合法的性质：左括号数量等于右括号；对于一个合法的括号字符串p,必然对于任何0<=i<len(p)都有：子串p[0...i]中的左括号数量都大于等于右括号数量
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(left: int, right: int, track: List[str], res: List[str]):
# 如果右括号数目小于左括号数目，说明当前组合是无效的，直接返回
if right < left:
return
# 如果左括号或右括号的数目小于 0，说明当前组合是无效的，直接返回
if left < 0 or right < 0:
return
# 如果左括号和右括号的数目都为 0，说明找到了一个有效的括号组合，将其加入结果列表 res 中
if left == 0 and right == 0:
res.append("".join(track))
return
# 尝试添加一个左括号到当前组合中，并进行递归调用
track.append('(')#选择
backtrack(left - 1, right, track, res)
track.pop() # 回溯，移除最后添加的左括号
# 尝试添加一个右括号到当前组合中，并进行递归调用
track.append(')')#选择
backtrack(left, right - 1, track, res)
track.pop() # 回溯，移除最后添加的右括号
if n == 0:
return []
track = [] # 用于追踪当前的括号组合
res = [] # 保存有效的括号组合
backtrack(n, n, track, res) # 调用回溯函数生成括号组合
return res # 返回结果列表