好的，我们这次来详细讲解 LeetCode 第 22 题「括号生成」。

1. 题目描述

题目：数字 n 代表生成括号的对数，请你设计一个函数，生成所有可能并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

约束条件：1 <= n <= 8

2. 题意理解

• 我们需要生成所有长度为 2n 的字符串，由 '(' 和 ')' 组成。
• 这个字符串必须是一个 有效的括号字符串，即：
  1. 左右括号数量相等（各为 n）。
  2. 对于字符串的任意前缀，左括号的数量 大于等于 右括号的数量（否则会出现无效匹配，比如 ")(" 就不合法）。

3. 思路分析

3.1 暴力法思路（先理解问题）

最直接的想法是：生成所有由 n 个 '(' 和 n 个 ')' 组成的字符串（全排列去重），然后逐个检查是否有效。
但是这样复杂度很高，因为总共有 \(C_{2n}^{n}\) 种排列，检查每个字符串是否有效需要 \(O(n)\) 时间，总复杂度约为 \(O(n \cdot \frac{(2n)!}{(n!)^2})\)，n 稍大就不可行。

3.2 回溯法（DFS）思路

我们可以在生成过程中就保证括号的有效性，避免无效分支，这就是 回溯法（DFS + 剪枝）。

关键变量：

• left：当前已使用的左括号数量。
• right：当前已使用的右括号数量。
• path：当前已生成的字符串。
• res：存储所有有效结果的列表。

规则：

1. 如果 left < n，可以加一个左括号 '('。
2. 如果 right < left，可以加一个右括号 ')'（因为右括号数量必须小于左括号数量，才能保证前缀有效）。
3. 当 left == n 且 right == n 时，说明生成了一个有效组合，加入结果列表。

4. 详细步骤推导（以 n=2 为例）

我们一步步手动推导 n=2 的情况，加深理解。

初始状态：left = 0, right = 0, path = ""

步骤 1：可以加 '('（因为 left < 2）
path = "(", left = 1, right = 0

步骤 2：可以加 '('（left < 2）
path = "((", left = 2, right = 0

步骤 3：不能加 '('（left 已满），可以加 ')'（right < left）
path = "(()", left = 2, right = 1

步骤 4：可以加 ')'（right < left）
path = "(())", left = 2, right = 2 → 得到一个结果 "(())"，回溯。

回溯到 path = "(" 时，另一个分支：加 ')'（right < left? 此时 left=1, right=0，可以加）
path = "()", left = 1, right = 1

步骤 5：加 '('（left < 2）
path = "()(", left = 2, right = 1

步骤 6：加 ')'
path = "()()", left = 2, right = 2 → 得到结果 "()()"。

最终结果：["(())", "()()"]。

5. 代码实现（Python）

def generateParenthesis(n):
    res = []
    
    def backtrack(path, left, right):
        # 如果左右括号都用完了，说明生成了一个有效组合
        if left == n and right == n:
            res.append(path)
            return
        
        # 可以加左括号的条件：已使用的左括号数小于 n
        if left < n:
            backtrack(path + '(', left + 1, right)
        
        # 可以加右括号的条件：已使用的右括号数小于左括号数
        if right < left:
            backtrack(path + ')', left, right + 1)
    
    backtrack("", 0, 0)
    return res

6. 复杂度分析

• 时间复杂度：\(O(\frac{4^n}{\sqrt{n}})\)，这是第 n 个卡特兰数（Catalan number）的量级，因为有效的括号组合数就是卡特兰数 \(C_n = \frac{1}{n+1} \binom{2n}{n}\)，每个组合生成需要 \(O(n)\) 时间（字符串拼接），但实际在回溯中我们通过传递 path 字符串，每次递归是 \(O(1)\) 或 \(O(n)\) 取决于实现，总体是 \(O(C_n)\) 数量级。
• 空间复杂度：\(O(n)\) 除了存储结果外，递归栈深度最大为 \(2n\)。

7. 总结

• 本题是经典的回溯问题，关键在于 在递归过程中通过条件剪枝，只生成有效的括号串。
• 剪枝条件：
  1. 左括号数不超过 n。
  2. 右括号数不超过左括号数。
• 这种方法避免了无效分支，效率远高于暴力生成再验证。

这样讲解清楚了吗？如果有哪里需要进一步展开，我可以继续补充。