22. 括号生成（中）

• 题目
• 题解：回溯+剪枝

题目

• 数字 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  # 返回结果列表