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

1. 题目描述

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

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

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

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

2. 题意理解

我们要生成所有长度为 2n 的括号字符串，并且它们必须 有效。
有效括号字符串的定义是：

1. 左括号 '(' 和右括号 ')' 数量相等（各为 n 个）。
2. 从左到右遍历时，任意位置 已出现的右括号数量 不能多于 已出现的左括号数量（否则意味着有右括号没有匹配到左括号）。

例如：n = 2 时：

• 有效："(())"、"()()"
• 无效："())("（右括号多于左括号）、")(()"（一开始右括号就多于左括号）。

3. 思路分析

3.1 暴力法思路（再优化）

最直接的想法是：生成所有由 n 个 '(' 和 n 个 ')' 组成的字符串（全排列去重），然后逐个检查是否有效。
但这样会生成很多无效字符串，检查成本高，复杂度太大（共有 \(\frac{(2n)!}{(n!)^2}\) 种排列，即卡特兰数 \(C_n\) 的量级）。

3.2 回溯法（DFS）思路

我们可以在生成过程中就保证有效性，避免无效分支。
定义两个计数器：

• open：当前已使用的左括号数量。
• close：当前已使用的右括号数量。

规则：

1. 如果 open < n，可以加一个左括号 '('。
2. 如果 close < open，可以加一个右括号 ')'。

这样能保证：

• 最终 open == close == n。
• 任何时候 close <= open（不会出现无效匹配）。

4. 逐步推导（以 n = 2 为例）

我们模拟回溯过程，用树形结构理解所有可能路径。

初始：open = 0, close = 0, 当前字符串 ""

第一层选择：

• 只能加 '('（因为一开始 close == open，不能加 ')'）
  得到 "("，open=1, close=0

第二层选择：

• 可以加 '('（因为 open=1 < n=2）
  得到 "(("，open=2, close=0
• 可以加 ')'（因为 close=0 < open=1）
  得到 "()"，open=1, close=1

我们按 DFS 深度优先遍历：

分支1：从 "((" 继续：

• 不能加 '('（open=2 已满）
• 可以加 ')' → "(()"，open=2, close=1
• 再加 ')' → "(())"，open=2, close=2 → 得到一个结果。

回溯到 "((" 再回溯到 "("。

分支2：从 "()" 继续：

• 可以加 '(' → "()("，open=2, close=1
• 再加 ')' → "()()"，open=2, close=2 → 得到另一个结果。

回溯到 "()" 时，还能加 ')' 吗？此时 close=1 与 open=1 相等，所以不能加 ')'（因为规则要求 close < open 才能加 ')'）。

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

5. 代码实现（回溯/DFS）

def generateParenthesis(n: int):
    result = []
    
    def backtrack(s, open_count, close_count):
        # 如果长度达到 2n，加入结果
        if len(s) == 2 * n:
            result.append(s)
            return
        
        # 可以加左括号的条件
        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)
        
        # 可以加右括号的条件
        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)
    
    backtrack("", 0, 0)
    return result

6. 复杂度分析

• 时间复杂度：\(O(2^{2n} / \sqrt{n})\) 或更精确说是 \(O(\frac{4^n}{\sqrt{n}})\)，因为结果是卡特兰数 \(C_n = \frac{1}{n+1} \binom{2n}{n} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\)，每个有效序列生成时间是 \(O(n)\)，但通常我们忽略构造字符串的线性部分，说成 \(O(C_n)\)。
• 空间复杂度：\(O(n)\) 除了结果存储外，递归栈深度最多 \(2n\)。

7. 其他思路（动态规划）

此题也可用 DP：
定义 dp[i] 表示使用 i 对括号的所有有效组合。
那么 dp[i] 可以由 "(" + dp[j] + ")" + dp[i-1-j]" 组合得到，其中 j 从 0 到 i-1。
但回溯法更直观。

8. 总结

• 核心是 在生成过程中通过 open ≥ close 来保证有效性。
• 回溯法通过两个计数变量剪枝，只走有效分支。
• 理解括号有效性的条件：任意前缀中 '(' 数量 ≥ ')' 数量，且最终两者数量相等。

这样一步步推导，就能掌握这个经典的回溯题目了。