Hot 100 --- 括号生成

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

一、题目

二、题目分析

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

比如 n = 3，输出：

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

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

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

思路概览

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—;
}
}
}

思路简要说明

三、思路详解

第一步：什么是有效括号

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

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

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

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

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

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

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

根
├─ 加(
│ ├─ 加(
│ │ ├─ 加(
│ │ │ ├─ 加( → (((( 无效
│ │ │ └─ 加) → (((( 无效
│ │ └─ 加)
│ │ ├─ 加( → (()( 有效
│ │ └─ 加) → (()) 有效 ✓
│ └─ 加)
│ ├─ 加(
│ │ ├─ 加( → ()(( 无效
│ │ └─ 加) → ()() 有效 ✓
│ └─ 加)
│ ├─ 加( → ())( 无效
│ └─ 加) → ())) 无效
└─ 加)
├─ 加(
│ ├─ 加(
│ │ ├─ 加( → )((( 无效
│ │ └─ 加) → )(() 无效
│ └─ 加)
│ ├─ 加( → )()( 无效
│ └─ 加) → ())) 无效
└─ 加)
├─ 加(
│ ├─ 加( → ))(( 无效
│ └─ 加) → ))() 无效
└─ 加)
├─ 加( → )))( 无效
└─ 加) → )))) 无效

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

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

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

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

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 时自动跳过加右括号的分支，直接砍掉整棵无效子树，不用遍历到叶子再判断

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

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

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

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

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

if(open < n) {
sb.append('('); // 开一个左括号
open++; // 左括号计数器+1
backTrack(n); // 递归
sb.deleteCharAt(sb.length() – 1); // 回溯撤销
open—;
}

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

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

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

if(close < open) {
sb.append(')'); // 关一个右括号
close++; // 右括号计数器+1
backTrack(n); // 递归
sb.deleteCharAt(sb.length() – 1); // 回溯撤销
close—;
}

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

第五步：完整执行过程

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

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] 处回溯后选右形成 (() 开头，③ 在 (() 右边再选右形成 (()) 开头，④⑤ 在一开始就选右形成 () 开头

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

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

复杂度分析

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