本文概览：本文以LeetCode题目"括号生成"为例，讲解回溯法在按规则生成括号组合中的应用，以及如何保证生成的全部是有效括号
一、题目
二、题目分析
题目要求：给定一个整数 n，生成所有由 n 对括号组成的有效括号组合
比如 n = 3，输出：
1
| ["((()))", "(()())", "(())()", "()(())", "()()()"]
|
什么是有效括号？三个条件：
- 左括号总数 = 右括号总数 = n
- 任何前缀中，左括号数 ≥ 右括号数（不能先出现右括号再出现左括号）
- 括号必须正确关闭（不能出现
)( 这种）
暴力做法也是回溯——决策树每个节点都有两个分支（加左括号 / 加右括号），无限制地生成 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;
}
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--;
}
}
}
|
思路简要说明
- 两个计数器：open 记录用了多少个左括号，close 记录用了多少个右括号
- 两个添加规则：open < n 时可以加左括号；close < open 时可以加右括号
- 收集条件：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++;
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++;
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 个字符
