括号生成与回溯算法：从剪枝到卡特兰数的完整推导

1. 这道题到底在考什么：从"括号"看穿树形决策的本质

LeetCode 22 号题"括号生成"，我刷了三遍才真正觉得自己会了。第一遍背代码，第二遍看懂，第三遍才敢说理解。这东西表面是字符串题，面试官真正想看的，是你有没有把"生成过程"抽象成"决策过程"的能力。

先看题目本身：给定 n 代表括号的对数，生成所有可能的并且有效的括号组合。n=3 时输出应该是这五组：

((())) (()()) (())() ()(()) ()()()

注意排序不重要，重要的是"所有"和"有效"两个词。很多人第一反应是：括号就左右两种，一共 2n 个位置，每个位置要么左要么右，直接枚举不就行了？理论上没错，但 n=3 时就有 2^6=64 种组合，最终只有 5 种合法，大部分时间都在做无用功。

这道题真正考察的模型，是一个带约束的树形决策。你可以把 2n 个位置看成一条从根到叶子的路径，每一步有两个选择：放左括号还是右括号。问题从"枚举所有字符串"变成"在决策树上走出一条满足约束条件的路径"，后者正是回溯算法（Backtracking）的典型应用场景。

为什么我说它是模型而不是字符串题？因为同样的决策结构，换一层皮就是其他题：n 对括号对应 n 次入栈出栈、二叉树的 n 个节点形态数量、矩阵连乘的加括号方式……理解了这个模型，你刷的就不只是一道题，而是一类题。

对基础不同的读者我的建议是：如果你是第一次接触回溯，先把本文第 3 节剪枝条件的推导看懂；如果你已经会做了，直接跳到第 6 节和第 7 节，那部分是我反复踩坑后的经验总结。

2. 先从最笨的方法说起：暴力枚举的完整推导与它的致命短板

2.1 暴力法怎么写：所有组合 + 逐条验证

暴力法思路很直白：先生成所有可能的长度为 2n 的括号串，再筛出合法的。生成所有组合可以用递归，也可以用一个简单的二进制掩码思路——每个位置两种选择，总共 2^(2n) 种，比如 n=3 就是 64 种。

然后是验证。验证一个括号串是否有效，核心是一个变量 balance：

• 遇到(，balance 加 1；
• 遇到)，balance 减 1；
• 过程中如果 balance 变成负数，直接失效；
• 结束时候 balance 必须等于 0。

以())(()为例，扫到第三个字符)时 balance=-1，立刻淘汰。这个验证逻辑很简单，但它揭示了一件事：括号合法的本质，是任意前缀中右括号不能多于左括号，且最终左右数量相等。

用代码表达大概是：

def is_valid(s): balance = 0 for ch in s: if ch == '(': balance += 1 else: balance -= 1 if balance < 0: return False return balance == 0 def generate_parenthesis_brute(n): res = [] def backtrack(path): if len(path) == 2 * n: if is_valid("".join(path)): res.append("".join(path)) return path.append('(') backtrack(path) path.pop() path.append(')') backtrack(path) path.pop() backtrack([]) return res

这段代码其实是"不带剪枝的递归枚举"，它把 64 条路全走完了再筛选。结果自然只有 5 条能通过验证。

2.2 暴力法的复杂度为什么不能忍

暴力法的复杂度是 O(2^(2n) · n)：生成 2^(2n) 个字符串，每个字符串验证需要 O(n)。这个增长速度有多可怕？我列个表你直观感受一下：

n	枚举总数 2^(2n)	验证开销（约）	合法结果数（卡特兰数）
3	64	384	5
5	1,024	5,120	42
8	65,536	524,288	1,430
10	1,048,576	10,485,760	16,796
15	1,073,741,824	16,109,127,360	9,694,845

n=15 时已经要枚举 10 亿个字符串，哪怕每微秒处理一个，也要十几分钟。而合法结果只有 969 万。换句话说，大量时间花在了注定无效的序列上。

2.3 暴力法的真正价值：当基准，不当事后笑话

我不会否认暴力法的价值。写算法题时，我的习惯是先暴力，再优化。暴力解法代码短、逻辑简单，尤其适合做测试基准——回溯解法写完，拿 n=3、n=4 和暴力结果对拍，能立刻确认剪枝逻辑没有漏掉答案。

另一个价值是帮助理解"为什么需要剪枝"。当我第一次画出 n=3 的暴力递归树，再画出剪枝后的递归树，才真正明白剪枝省掉的不是一两个节点，而是一整片一整片的无效子树。

3. 回溯剪枝的两个条件是怎么来的：递归树的形态与边界判断

3.1 两个剪枝条件的完整推导

回溯相比暴力的核心区别在于：**等发现路径无效再回头，不如在每一步就判断这条路值不值得走下去。**放到括号生成里，就是递归进入下一层之前就检查两个条件。

条件一：还能放左括号吗？

• 如果已经用了 open 个左括号，只要 open < n，就可以继续放(。因为每对括号需要一个左括号，n 对就需要 n 个左括号，没到 n 个就能放。

条件二：还能放右括号吗？

• 如果已经用了 close 个右括号，只有 close < open 时才可以放)。因为右括号不能比左括号多——否则当前前缀必然无法成为合法序列。

这两个条件哪个可以省？理论上都不能省。你可以试试只剪条件一不剪条件二：当 open 已经等于 n，还能继续放右括号，最终会生成什么？((()))之后又出现(()))这种整个串长度都是 2n+1 的东西，直接越界。反过来只剪条件二不剪条件一：会一直放左括号直到放无可放，右括号又因为 close < open 一直有机会补，最终生成一个 balance 恒非负的合法串——但 open 超过 n 意味着左括号数量大于右括号，balance 为 0 时序列长度超过 2n，结果还是错的。

正确的组合是：右括号受左括号数量约束，左括号受 n 约束，两者缺一不可。

3.2 递归树的形态：剪枝到底砍掉了什么

我用 n=2 画一个决策树的文字版，帮助你理解剪枝前后的差异。

暴力枚举的树：

"" / \ ( ) / \ / \ ( ) ( ) / \ / \ / \ / \ ( )...（共 16 个叶子）

剪枝后的树：

"" / ( / \ ( ) / \ ( ) / ) / )

看到区别了吗？第一个节点就只剩一个分支了，因为初始时 close=0、open=0，第二个条件close < open是 0 < 0，不成立，所以)从一开始就被否决。这直观说明：第一个字符永远是(，因为任何合法括号串第一个字符不可能是右括号。剪枝条件在不知不觉中，就把这些显而易见的无效路径全都排除了。

递归树每一层的节点状态，可以表示成(open, close)二元组。根是 (0,0)，每放一个左括号 open+1，每放一个右括号 close+1。剪枝规则翻译成状态转移就是：

• 从 (open, close) 可以转移到 (open+1, close)，当且仅当 open < n；
• 可以转移到 (open, close+1)，当且仅当 close < open；
• 当 open == n 且 close == n 时，到达合法叶子。

3.3 为什么这样剪不会漏答案

这是面试时考官一定会追问的点。答案在于这两个条件是合法括号串前缀的必要条件。任何合法的完整括号串，它的任意前缀一定满足"左括号数 ≥ 右括号数"，整体满足"左括号数 = 右括号数 = n"。我们的剪枝条件只排除不满足必要条件的路径，而所有满足条件的路径都会被完整探索，所以一定不会漏掉任何一个合法结果。

说得更直白一点：我们没有武断地砍掉任何可能包含答案的子树，只是在"知道它肯定错"的时候提前止损。

3.4 终止条件怎么定

到达叶子有两种判断方式。一种是open == n && close == n，另一种是sb.length() == 2 * n。我推荐前者，语义更清晰，也避免每次递归都调一次 length()。当两个计数都到 n，说明左右括号都用完了，当前拼接出来的串就是一个合法结果，加入结果集，返回。

4. 代码落地：三套主流实现与逐行解读

4.1 Java 版：StringBuilder 回溯

这是面试中我写的最顺的版本：

public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); dfs(res, new StringBuilder(), 0, 0, n); return res; } private void dfs(List<String> res, StringBuilder sb, int open, int close, int n) { if (open == n && close == n) { res.add(sb.toString()); return; } if (open < n) { sb.append('('); dfs(res, sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1); // 回溯撤销 } if (close < open) { sb.append(')'); dfs(res, sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1); // 回溯撤销 } }

这里最容易被忽略的就是那两行deleteCharAt。StringBuilder 是可变对象，你往里面 append 之后，如果递归返回时不撤销，下一个分支看到的sb会带着上一个分支的残余内容。很多人第一次写会漏掉撤销，结果得到一堆长度超过 2n 的乱串。

4.2 Python 版：列表模拟栈

from typing import List class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] path = [] def dfs(open_cnt: int, close_cnt: int) -> None: if open_cnt == n and close_cnt == n: res.append("".join(path)) return if open_cnt < n: path.append("(") dfs(open_cnt + 1, close_cnt) path.pop() if close_cnt < open_cnt: path.append(")") dfs(open_cnt, close_cnt + 1) path.pop() dfs(0, 0) return res

Python 里path用 list，pop()负责撤销；"".join(path)在叶子处一次性拼接成字符串。逻辑和 Java 完全一致，只是语言换了一下。

4.3 JavaScript 版：闭包 + 数组模拟

var generateParenthesis = function (n) { const res = []; const path = []; function dfs(open, close) { if (open === n && close === n) { res.push(path.join("")); return; } if (open < n) { path.push("("); dfs(open + 1, close); path.pop(); } if (close < open) { path.push(")"); dfs(open, close + 1); path.pop(); } } dfs(0, 0); return res; };

JS 写法和 Python 几乎同构，闭包捕获path和res，递归函数不需要额外传参。注意path.pop()同样不能省。

4.4 String 版本：为什么我不用它

很多人图省事，直接传 String，比如dfs(str + "(", ...)，以为这样就不用撤销了。确实，String 是不可变对象，每次拼接都产生新对象，递归返回后原字符串自动"恢复"。但问题在于：

• 每次拼接str + "("都创建一个新 String，在 n 较大时产生大量临时对象；
• 叶子处还要把最顶层的str加入结果集，中间层的字符串对象全部变成垃圾，GC 压力大。

LeetCode 上 n 最大到 8，String 版也能过，但面试时如果 n 被放大到 15，性能差距就很明显。用 StringBuilder 回溯是更工程化的选择，也顺便展示了你对"对象可变性"的理解。

4.5 另一种解法：动态规划

回溯不是唯一解。动态规划思路是：dp[i]表示 i 对括号能生成的所有合法组合。递推关系是：

dp[i] = "(" + dp[j] + ")" + dp[i-1-j] ，其中 0 <= j < i

含义是：最外层的那对括号，把剩下的 i-1 对括号分成了"内部"和"后面"两部分。内部放 j 对，后面放 i-1-j 对，遍历所有 j 的组合。Java 实现：

public List<String> generateParenthesis(int n) { List<List<String>> dp = new ArrayList<>(); dp.add(List.of("")); // 0 对括号 for (int i = 1; i <= n; i++) { List<String> cur = new ArrayList<>(); for (int j = 0; j < i; j++) { for (String left : dp.get(j)) { for (String right : dp.get(i - 1 - j)) { cur.add("(" + left + ")" + right); } } } dp.add(cur); } return dp.get(n); }

动态规划的好处是不用手动撤销，思路也很数学化；缺点是引入了额外的存储，空间复杂度比回溯高一些。面试时如果能两种解法都写出来，会是明显的加分项。

5. 复杂度到底怎么算：卡特兰数、递归节点数与那坨让人头疼的 O(4^n/√n)

5.1 合法结果数：卡特兰数

先说结论：n 对括号的合法组合数量，等于第 n 个卡特兰数：

C_n = (1 / (n+1)) * C(2n, n) = (2n)! / ((n+1)! * n!)

n=3 时 C_3 = (1/4) * 20 = 5，正好对上；n=4 时 14，n=5 时 42。这个公式不用死记，你需要知道的是它来自哪里。卡特兰数在很多组合计数问题中出现，括号配对只是它的一种等价表述。我建议把((()))这种结构理解成"先出栈的元素比后出栈的元素更晚入栈"这一大类问题的统一形态。

5.2 时间复杂度：为什么是 O(4^n / √n)

回溯的时间复杂度不能简单地写成"结果数 × 每个结果的构造时间"。不过主项确实是这两者的乘积。每个合法结果长度为 2n，从根到叶子要走 2n 层递归，每一层做 O(1) 的 append 和 delete，所以单条路径的构造时间是 O(n)。结果数是 C_n，于是总时间的主项是：

O(n * C_n)

把卡特兰数的斯特林近似带进去：

C_n ≈ 4^n / (n^(3/2) * sqrt(π))

乘上 n 之后：

O(n * 4^n / (n^(3/2))) = O(4^n / sqrt(n))

所以网上常见的O(4^n / √n)就是这么来的。严格来说，回溯还会探索一些最终没有构成合法结果的"半合法前缀"节点，但那些节点的数量级不会超过合法路径总数的常数倍，最终的时间复杂度仍然由上面这个式子主导。

5.3 空间复杂度怎么答

空间复杂度要分两部分看：

• 递归栈的深度是 2n，所以栈空间 O(n)；
• 如果不把结果集计入空间（面试时可以说"不计输出空间"），返回前只保留一条 path，空间就是 O(n)；
• 如果计算结果集本身占用的空间，每个结果长度 2n，结果是 C_n 个，输出空间 O(n · C_n)。

面试官问你空间复杂度时，先说"O(n) 的递归栈 + 结果集除外"，再补一句"如果把结果集也算上，是 O(n·C_n)"，这样既准确又显得你有边界意识。

5.4 亲身验证：n=10 时的体感

我实际跑过 n=10，回溯版耗时几十毫秒，暴力版要跑几十秒。n 再大一档，暴力版基本没法用了。这个体感差异比任何复杂度公式都来得直观。在面试或者实际项目中，你永远应该选择"尽可能早地砍掉不可能的分支"这种思路。

6. 从"会做"到"写对"：易错点、边界条件与调试技巧

6.1 五个高频翻车点

第一个：忘掉撤销。StringBuilder 或 list 路径不 pop，导致兄弟分支串味。这是最长见的错误，没有之一。

第二个：剪枝条件方向写反。有人写成if (close > open)，然后递归全部乱套。写成close < open才对，语义是"只有右括号还不够的时候才补充右括号"。

第三个：终止条件写成len == n或者open == n。前者提前结束，只生成长度为 n 的序列；后者少了 close 也达到 n 的检查，会在 close 超限后继续递归。

第四个：n=0 时返回什么。[,]还是[""]？题目明确 n 是正整数的话不用管，但有些变体题会问 n=0，那时候要约定返回[""]（空字符串代表零对括号的一种组合），而不是空列表。

第五个：对res.add(sb.toString())的位置理解不到位。必须在叶子处 add。如果放在(open < n)分支内部，会提前把不完整的序列存下来，结果全是"半成品"。

6.2 边界用例一览

输入	期望输出	说明
n=0	[""]（部分题设）	空串也是一对都没有的唯一组合
n=1	["()"]	唯一合法组合
n=2	["(())", "()()"]	两种合法组合
n=3	5 种	教材级用例
n=8	1,430 种	LeetCode 默认上限

6.3 调试技巧：打印递归树状态

我第一次写回溯时总是不确定剪枝对不对，后来学会一招：递归入口打印当前 open、close、path。n=2 时的输出大致是：

open=0 close=0 path= open=1 close=0 path=( open=2 close=0 path=(( open=2 close=1 path=(() open=2 close=2 path=(()) open=1 close=1 path=() open=2 close=1 path=()( open=2 close=2 path=()()

看一眼递归路径，立刻就能发现哪些分支被剪掉了，哪些走重了。对新手来说，这个可视化的价值比任何注释都大。

6.4 如何向面试官解释你的代码

我复盘自己面试时，发现一个好的口头表述是:"我把这个过程看成走迷宫，每一步要么放左括号，要么放右括号，但放右括号之前必须确认当前右括号的数量还没追上左括号。当左右括号都用完时，当前路径就是一个合法解。然后撤销这一步的选择，继续尝试另一个方向。" 这个说法既描述了回溯的本质，又说明了剪枝依据，面试官通常能直接 get 到你的思路。

7. 这道题不是一个孤岛：括号类题型的血缘关系与迁移价值

7.1 括号家族的题谱

括号生成的思路，能直接迁移到好几道 LeetCode 题上：

• LeetCode 20 有效括号：给一个字符串判断是否合法，用栈或计数器，是第 2 节验证逻辑的直接应用。
• LeetCode 32 最长有效括号：求最长的合法括号子串，需要 DP 或栈，难度直接上一个台阶。
• LeetCode 301 删除无效的括号：给定含非法括号的字符串，删掉最少的字符使其合法，返回所有结果。这道题本质上是"反向生成"：先统计需要删除的左右括号数量，再带着计数做回溯。
• LeetCode 678 有效的括号字符串：带*通配符的变体，用双栈或 DP。

做完括号生成后再做这几道，你会发现自己对各种括号约束的敏感度高了很多。

7.2 卡特兰数的其他等价形态

括号组合的数量和下面这些经典问题的答案，数学上是同一个数：

• n 个元素的出栈序列数量；
• n 个节点能构成的不同二叉树的形态数；
• 凸 n+2 边形的三角形划分方法数；
• 从 (0,0) 到 (n,n) 不越过对角线的路径数。

知道这层联系有什么用？面试如果深挖，你可以通过括号生成引出"卡特兰数"这个话题，展示知识广度。我从个人经验说，这种关联思维在算法轮非常加分，因为大部分候选人只会背模板。

7.3 把括号生成的思路用到别的组合搜索题

括号生成是典型的"约束组合搜索"问题。同一类套路可以迁移到：

• 全排列：需要一个 used 数组避免重复使用同一元素；
• 组合总和：排序 + 剪枝；
• N 皇后：判断列、对角线是否冲突；
• 子集：每个元素选或不选。

这些题共用的框架都是"递归 + 路径 + 撤销"，差别只在于约束条件怎么定义。括号生成恰好是"约束条件最简单、最直观"的那一道，所以非常适合作为回溯入门的敲门砖。一旦你彻底吃透了它，后面遇到 n 皇后、解数独这类复杂约束题，至少不会害怕。

7.4 我个人的一点建议

刷题不是刷数量，是刷模型的连接。括号生成这道题我建议你至少做三遍：第一遍照着答案写，第二遍不看答案独立写，第三遍隔两周回来用另一种解法（动态规划）再写一遍。第三遍的时候，你会发现原来背的代码已经断了，能用语言清晰地讲出自己的思路，那才是真会了。

尝试用这道题去串起整个括号家族，再去串起回溯算法这个大框架。刷题到后期，你手里握的不是一道一道孤立的题，而是一张互相连接的网——括号生成就是这张网里非常值得锚定的一个节点。