括号生成（LeetCode 22，Medium）是回溯的第二课：给 n 对括号，生成所有合法的组合。本库《全排列》教了回溯骨架（选择→递归→撤销），这道题在骨架上加了新东西：约束——不是所有生成结果都合法，而且回溯的每一步都可以用约束提前剪枝。它示范了「约束回溯」的标准写法，以及剪枝带来的效率鸿沟。
约束回溯：两个计数器决定合法选择
合法括号串的判据可以变成两个计数器的规则：串中任意前缀，左括号数 ≥ 右括号数（否则出现非法的「右括号先于匹配左括号」）；总长 2n 时左右各 n 个。把这两条规则翻译成回溯每一步的合法选择：维护 left_used（已用左括号数）与 right_used（已用右括号数）——可以放左括号当且仅当 left_used < n；可以放右括号当且仅当 right_used < left_used（当前前缀仍是合法前缀）。递归到长度 2n 时收集结果。剪枝发生在选择枚举处：不合法的选择根本不会被枚举——回溯树在生长的每一刻都只长合法的分支：
def generate_parenthesis(n: int) -> list[str]:
result, path = [], []
def backtrack(left: int, right: int):
if len(path) == 2 * n: # 长度满：由剪枝保证必合法
result.append("".join(path))
return
if left < n: # 剪枝 1：还有左括号可用
path.append("(")
backtrack(left + 1, right)
path.pop()
if right < left: # 剪枝 2：右括号不能超过左括号
path.append(")")
backtrack(left, right + 1)
path.pop()
backtrack(0, 0)
return result
两个剪枝条件的正确性：剪枝 1（left < n）保证左括号不超量；剪枝 2（right < left）保证任意前缀合法——两者合起来，走到长度 2n 的每一条路径都自动合法（这就是为什么收集时不需要再验证合法性——约束已经内建在搜索树里）。
剪枝的效率鸿沟：「生成再过滤」vs「边生成边剪枝」
对照的反面写法：不带剪枝的暴力生成——每一步放「(」或「)」两种选择，生成长度 2n 的所有 2^(2n) 个串，最后逐个验证合法性（栈匹配）——结果是正确的，效率是天壤的。量化对比：n=3 时暴力生成 64 个串过滤出 5 个（浪费 59 个分支），剪枝版只走合法分支直接产出 5 个；n=10 时暴力是万亿级分支、剪枝版只有第 n 个卡特兰数（C(10) = 16796）个分支——差距随 n 指数放大。剪枝为什么这么有效：非法串的特征（某处右括号超前）会在生成过程的早期暴露——剪枝 2 在第一次「右超左」的瞬间就砍断整棵子树，而暴力生成要把整棵子树长完才发现。这就是「边生成边剪枝」与「生成再过滤」的效率鸿沟的根源：过滤是在叶子处检验，剪枝是在枝干处砍断——越早砍，砍掉的子树越大。这条规律是所有约束搜索问题（N 皇后的冲突检查、数独的格子合法性、单词搜索的路径约束）的共同纲领：约束检查的位置越靠近决策点，剪掉的子树越大——把合法性判断从「事后」搬到「事中」，是搜索问题优化的第一杠杆。
剪枝的正确性与「解的计数」：卡特兰数
剪枝版必须保证不重不漏——每个合法串恰好被生成一次。论证：合法串的每个前缀都满足「左 ≥ 右」，因此生成每个合法串的路径上，每一步的选择都满足两个剪枝条件（会被枚举）；而每一步的选择是确定的（放左或放右互斥），不同的合法串对应不同的选择序列——不重不漏成立。顺带一个优美的数学事实：合法串的数量是卡特兰数 C(2n, n)/(n+1)（n=3 时 5 个：((()))、(()())、(())()、()(())、()()()）——回溯搜索的解数量有闭式公式，是检验实现正确性的好标尺（跑一遍计数与卡特兰数对照）。卡特兰数在算法题中的出镜率极高（括号、出栈序列、凸多边形三角剖分、二叉树形态计数——本库《不同的二叉搜索树》同款），它们的共同本质是「带约束的嵌套/配对结构的计数」——认识这个家族，这些题就都成了「卡特兰数的变装」。
剪枝 vs 计数：同一个问题的两条路
括号生成的「解数量」问题有两条路：回溯枚举（本篇正文的剪枝生成，输出每个解）与卡特兰数的 DP 计数（只算数量不输出解）——两条路的对比揭示「枚举 vs 计数」的一般规律。回溯枚举：输出全部 5 个解（n=3），时间正比于「解的总量 × 解的长度」（生成每个串的成本）——它的价值是解本身；DP 计数：C[i] = Σ C[j]×C[i-1-j]（卡特兰数递推——枚举第一对匹配括号的位置切分），只算数量，时间 O(n²)——它的价值是数量本身。什么时候用哪条：题目要输出方案 → 只能枚举；只要数量（哪怕巨大）→ 计数（n=100 的卡特兰数，DP 算得出、枚举算不出）；数量巨大但只展示前几个 → 枚举 + 生成器（惰性输出）。两条路的深层联系：DP 计数的递推式（第一对括号的位置切分）就是回溯树的「第一层决策」的计数版——回溯树的每一层决策，对应 DP 的一个求和项——「枚举树」与「计数递推」是同一个组合结构的两种投影；这个对偶视角，是从「会写回溯」到「会算组合」的桥梁。
合法括号与 Dyck 路径：卡特兰的其他面目
合法括号串还有一个优美的几何解释：Dyck 路径——把左括号看作「上一步」、右括号看作「下一步」，合法括号串就是一条「从地面出发、始终不低于地面、最终回到地面」的折线。这个几何视角的三层价值：其一，可视化了剪枝条件——本篇正文的剪枝 2（right < left）的几何意义是「折线不能钻到地面以下」——违反即出界的直觉让剪枝的正确性「看得见」。其二，连接了卡特兰数的几何家族——出栈序列（栈的折线同款）、凸多边形三角剖分、二叉搜索树的形态计数——它们全部计数为卡特兰数，因为它们都是「合法嵌套/配对结构」的不同投影。其三，揭示了「为什么是除以 n+1」——卡特兰数等于 C(2n,n) 除以 (n+1)，除法的组合意义是「从所有折线中，剔除钻到地下的」（反射原理的证明——把第一次钻到地下的部分沿地下镜像反射，与「终态在地下一格」的折线一一对应——总折线数减去坏折线数即卡特兰数）。反射原理是这个家族最美的证明——它把「合法性约束」的计数转化为「全部减去越界」的减法，一招通吃所有带下界约束的路径计数。
剪枝的两种风格：枚举时剪与 DP 计数——同一问题的两条路
括号生成的「解数量」问题有两条路：回溯枚举（本篇正文的剪枝生成，输出每个解）与卡特兰数的 DP 计数（只算数量不输出解）——两条路的对比揭示「枚举 vs 计数」的一般规律。回溯枚举：输出全部 5 个解（n=3），时间正比于「解的总量 × 解的长度」——它的价值是解本身。DP 计数：卡特兰数递推 C[i] 为多个 C[j] 与 C[i-1-j] 乘积的和（枚举第一对匹配括号的位置切分），只算数量，时间 O(n²)——它的价值是数量本身。什么时候用哪条：题目要输出方案 → 只能枚举；只要数量 → 计数（n=100 的卡特兰数，DP 算得出、枚举算不出）；数量巨大但只展示前几个 → 枚举 + 生成器（惰性输出）。两条路的深层联系：DP 计数的递推式（第一对括号的位置切分）就是回溯树的「第一层决策」的计数版——回溯树的每一层决策，对应 DP 的一个求和项——枚举树与计数递推是同一个组合结构的两种投影；这个对偶视角，是从会写回溯到会算组合的桥梁。
剪枝 vs 计数：同一问题的两条路
括号生成的解数量问题有两条路：回溯枚举（本篇正文的剪枝生成，输出每个解）与卡特兰数的 DP 计数（只算数量不输出解）——两条路的对比揭示枚举与计数的一般规律。回溯枚举：输出全部 5 个解（n=3），时间正比于解的总量乘以解的长度——它的价值是解本身。DP 计数：卡特兰数递推，只算数量，时间 O(n²)——它的价值是数量本身。什么时候用哪条：题目要输出方案则只能枚举；只要数量则计数（n=100 的卡特兰数 DP 算得出而枚举算不出）；数量巨大但只展示前几个则枚举加生成器惰性输出。两条路的深层联系：DP 计数的递推式就是回溯树的第一层决策的计数版——回溯树的每一层决策对应 DP 的一个求和项——枚举树与计数递推是同一个组合结构的两种投影；这个对偶视角是从会写回溯到会算组合的桥梁。
剪枝与「搜索树的效率」的量化
括号生成的回溯搜索有一个效率量化的方法值得学习。搜索树的节点数：不剪枝时是 2^(2n)（每个位置两种选择）；加剪枝后是卡特兰数 × 2n（每个合法解的路径长度 2n）——剪枝把搜索树从指数级压缩到卡特兰级。量化剪枝效果的方法：剪枝效率 = 不剪枝的节点数 ÷ 剪枝后的节点数 = 2^(2n) / (C(n) × 2n)——这个比值随 n 指数增长，说明剪枝的效果随 n 增大越来越显著。另一个度量：每个节点的「平均产出」——不剪枝时大量节点是无用的（不合法的串），剪枝后每个节点都对应一个合法前缀——节点的「信息密度」大幅提升。剪枝效率的量化方法可以推广到所有回溯题：比较剪枝前后的节点数，比值就是剪枝的加速比——它是衡量回溯实现质量的核心指标。
小结
这篇收成四条：约束回溯的写法——两个计数器（left_used/right_used）把合法性翻译成每步的合法选择枚举，「可以放左」与「可以放右」两个条件就是剪枝本身；走到满长度的路径自动合法，收集时无需再验证——约束已内建在搜索树里；「生成再过滤」与「边生成边剪枝」的效率鸿沟随 n 指数放大——过滤在叶子检验，剪枝在枝干砍断，越早砍砍掉的子树越大；解数量的卡特兰数是检验实现的好标尺——带约束的嵌套/配对计数家族，本质都是卡特兰数的变装。
参考资料
- LeetCode 22. Generate Parentheses —— 题目与官方题解
- 本库前篇：《LeetCode 46. 全排列：回溯算法的第一课》《LeetCode 51. N 皇后》—— 回溯系列
- 卡塔兰数（Catalan number）—— 解数量闭式公式的数学出处
读者留言
COMMENTS 暂无还没有留言，来说第一句？