本文概览：本文以LeetCode题目"括号生成"为例，讲解回溯法在按规则生成括号组合中的应用，以及如何保证生成的全部是有效括号

一、题目

括号生成题目

二、题目分析

题目要求：给定一个整数 n，生成所有由 n 对括号组成的有效括号组合

比如 n = 3，输出：

1
["((()))", "(()())", "(())()", "()(())", "()()()"]

什么是有效括号？三个条件：

  1. 左括号总数 = 右括号总数 = n
  2. 任何前缀中，左括号数 ≥ 右括号数（不能先出现右括号再出现左括号）
  3. 括号必须正确关闭（不能出现 )( 这种）

暴力做法也是回溯——决策树每个节点都有两个分支（加左括号 / 加右括号），无限制地生成 2^(2n) 种组合。优化做法就是给回溯加剪枝条件，只走有效的分支，直接跳过违反规则的组合

思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Test {
    private int close = 0;
    private int open = 0;
    private final StringBuilder sb = new StringBuilder();
    private final List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        backTrack(n);
        return result;
    }

    private void backTrack(int n) {
        // 递归终止条件
        if(sb.length()==n*2){
            result.add(sb.toString());
            return;
        }

        // 递归过程

        // 打开括号的个数不能大于n
        if(open<n) {
            sb.append('(');
            open++;
            backTrack(n);
            sb.deleteCharAt(sb.length() - 1);
            open--;
        }

        // 关闭括号的个数不能大于打开括号的个数
        if(close<open){
            sb.append(')');
            close++;
            backTrack(n);
            sb.deleteCharAt(sb.length()-1);
            close--;
        }
    }
}

思路简要说明

  1. 两个计数器：open 记录用了多少个左括号，close 记录用了多少个右括号
  2. 两个添加规则：open < n 时可以加左括号；close < open 时可以加右括号
  3. 收集条件：sb.length() == n * 2 时，所有括号用完，收集结果

三、思路详解

第一步：什么是有效括号

先明确有效括号的定义。拿 n = 2 来说：

1
2
3
4
5
6
7
有效：()
      (())
      ()()
无效：(     ← 没关闭
      )     ← 开头就是右括号，前面没有左开口
      )()   ← 开头就有右括号
      ())(  ← 第三个 ) 之前左括号已经用完，close > open

核心原则：从左往右扫描时，已经出现的右括号数永远不能超过左括号数，且最终左右相等

第二步：从暴力回溯到剪枝优化

本题所有解法都是回溯，区别在于剪枝条件。先把暴力回溯和优化回溯放在一起对比：

暴力回溯（无剪枝）：决策树每个节点都有两个分支（加左/加右），没有选择条件

以 n = 2 为例，暴力回溯的决策树有 2⁴ = 16 种排列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
根
├─ 加(
│   ├─ 加(
│   │   ├─ 加(
│   │   │   ├─ 加(     → ((((    无效
│   │   │   └─ 加)     → ((((    无效
│   │   └─ 加)
│   │       ├─ 加(     → (()(    有效
│   │       └─ 加)     → (())    有效  ✓
│   └─ 加)
│       ├─ 加(
│       │   ├─ 加(     → ()((    无效
│       │   └─ 加)     → ()()    有效  ✓
│       └─ 加)
│           ├─ 加(     → ())(    无效
│           └─ 加)     → ()))    无效
└─ 加)
    ├─ 加(
    │   ├─ 加(
    │   │   ├─ 加(     → )(((    无效
    │   │   └─ 加)     → )(()    无效
    │   └─ 加)
    │       ├─ 加(     → )()(    无效
    │       └─ 加)     → ()))    无效
    └─ 加)
        ├─ 加(
        │   ├─ 加(     → ))((    无效
        │   └─ 加)     → ))()    无效
        └─ 加)
            ├─ 加(     → )))(    无效
            └─ 加)     → ))))    无效

16 个叶子中只有 2 个有效：(()) 和 ()()。大量分支无效，浪费严重

优化回溯（加剪枝）：给回溯加两个剪枝条件，只走有效分支：

  • open < n：左括号没用完才能加左括号
  • close < open：右括号数不能超过左括号数，保证任何前缀中右括号始终少于左括号

n = 2 时，加了剪枝后的决策树只有有效分支：

1
2
3
4
5
6
7
8
9
backTrack(open=0, close=0)
├─ open<2 ✓ → 选( [o=1]
│   ├─ open<2 ✓ → 选( [o=2]
│   │   └─ close<open ✓ → 选) [c=1]
│   │       └─ close<open ✓ → 选) → "(())" ✓ ①
│   └─ close<open ✓ → 选) [c=1]
│       └─ open<2 ✓ → 选( [o=2]
│           └─ close<open ✓ → 选) → "()()" ✓ ②
└─ close<open ✗ (0<0)

每一层都先检查 open<n，再检查 close<open。根节点 open=0，两个条件中 open<2 ✓ 通过，close<open ✗ 跳过，所以只有加左括号一条路。到 [o=1] 时两个条件都通过，产生两种括号排列

剪枝的作用就是在 open=n 时自动跳过加左括号的分支，在 close=open 时自动跳过加右括号的分支，直接砍掉整棵无效子树，不用遍历到叶子再判断

以搜索 "(())" 为例，对比暴力回溯和剪枝回溯走过的路径：

1
2
3
4
5
6
7
8
暴力（无剪枝，每步都走(和)两个分支）：  剪枝：
(                                      ( [o=1]
  (                                      ( [o=2]
    ( → 全走左，4个左括号）无效            open<2 ✗
    ) [pos=2]                             close<open ✓ → ) [c=1]
      ( → "(()(" 无效                      open<2 ✗
      ) → "(())" ✓                        close<open ✓ → ) [c=2]
                                            → "(())" ✓

左边走了 4 条分支才到正确结果，右边直接在递归过程中通过条件跳过无效分支

第三步：左括号的剪枝条件

左括号的条件是 open < n，即还没用完 n 个左括号。这个条件剪掉了"左括号数量超过 n"的分支：

1
2
3
4
5
6
7
if(open < n) {
    sb.append('(');    // 开一个左括号
    open++;            // 左括号计数器+1
    backTrack(n);      // 递归
    sb.deleteCharAt(sb.length() - 1);  // 回溯撤销
    open--;
}

为什么先选左括号？因为有效括号必须以左括号开头。先走左分支，生成的是全左括号开头的组合（如 n=3 时先走 ((()))），然后回溯换右括号，生成 (()()) 等组合

第四步：右括号的剪枝条件

右括号的条件是 close < open，即已经开过的左括号还没关完。这个条件剪掉了"右括号数超过当前左括号数"的分支：

1
2
3
4
5
6
7
if(close < open) {
    sb.append(')');    // 关一个右括号
    close++;           // 右括号计数器+1
    backTrack(n);      // 递归
    sb.deleteCharAt(sb.length() - 1);  // 回溯撤销
    close--;
}

close < open 这个条件保证了任何前缀中右括号数不超过左括号数，永远不会出现 )( 这种无效情况

第五步：完整执行过程

n = 3 时，同样是每层先检查 open<3，再检查 close<open，只走通过的条件分支：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
backTrack(open=0, close=0)
├─ open<3 ✓ → 选( [o=1]
│   ├─ open<3 ✓ → 选( [o=2]
│   │   ├─ open<3 ✓ → 选( [o=3]
│   │   │   └─ close<open ✓ → 选) [c=1]
│   │   │       └─ close<open ✓ → 选) [c=2]
│   │   │           └─ close<open ✓ → 选) → ① "((()))"
│   │   └─ close<open ✓ → 选) [c=1]
│   │       ├─ open<3 ✓ → 选( [o=3]
│   │       │   └─ close<open ✓ → 选) [c=2]
│   │       │       └─ close<open ✓ → 选) → ② "(()())"
│   │       └─ close<open ✓ → 选) [c=2]
│   │           └─ open<3 ✓ → 选( [o=3]
│   │               └─ close<open ✓ → 选) → ③ "(())()"
│   └─ close<open ✓ → 选) [c=1]
│       ├─ open<3 ✓ → 选( [o=2]
│       │   ├─ open<3 ✓ → 选( [o=3]
│       │   │   └─ close<open ✓ → 选) [c=2]
│       │   │       └─ close<open ✓ → 选) → ④ "()(())"
│       │   └─ close<open ✓ → 选) [c=2]
│       │       └─ open<3 ✓ → 选( [o=3]
│       │           └─ close<open ✓ → 选) → ⑤ "()()()"
└─ close<open ✗ (0<0)

5 个结果：["((()))", "(()())", "(())()", "()(())", "()()()"]

和 n=2 的模式完全一致——每一层先选左再选右，到达上限的自动跳过。① 走到底全是左再全是右，② 在 [o=2] 处回溯后选右形成 (() 开头，③ 在 (() 右边再选右形成 (()) 开头，④⑤ 在一开始就选右形成 () 开头

第六步：和前面题目的对比（剪枝视角）

全排列 子集 组合总和 括号生成
每次可选范围 所有未选 start 往后 start 往后 open< n / close<open
剪枝条件 visited 跳过已选 无 sum > target 时剪枝 open< n 和 close<open
回溯对象 visited+path path path+sum sb+open+close
收集时机 叶子节点 每次进入 sum==target length==2n

括号生成的特点：不是遍历固定数组，而是按规则生成括号，剪枝条件是运行时的计数器状态（open/close），不像前面题目的剪枝条件基于固定的集合或数值

复杂度分析

  • 时间复杂度：O(4ⁿ / √n)，这是第 n 个卡特兰数的时间复杂度，n=3 时有 5 个结果，n=4 时有 14 个
  • 空间复杂度：O(n)，递归深度最大为 2n，StringBuilder 最多存 2n 个字符