刷 LeetCode 的人迟早都会遇到“括号生成”这道题。它在 LeetCode 热题 100 里排得上号面试出现的频率也不低而且它几乎就是为 DFS 回溯量身定做的一道题。很多人一开始看到这道题会被“生成所有合法括号组合”这个描述唬住以为要用什么高深的 DP 或状态机其实本质就是在搜索树上做了一次了不起眼的剪枝。这篇我就把这道题的 DFS 回溯解法从头到尾掰开揉碎地讲清楚包括题目让你在考什么、代码怎么写、为什么这么写、以及我在实际刷题和面试中踩过的坑。这道题适合谁看适合刚接触回溯算法、做过几道二叉树题目但还没怎么写过“搜索类”题目的读者也适合那些已经会用递归但搞不清“回”这个动作到底要回什么的人。如果能把这道题吃透你看全排列、子集、组合总和这些经典回溯题都会顺手很多。因为这道题表面上是在处理括号本质上是在强迫你理解“搜索树的约束条件到底长在哪里”。1. 先看懂题目合法括号组合到底在考什么1.1 题目到底让我们做什么题目给定数字 nn 代表括号的对数。请你生成所有可能的并且有效的括号组合。举个例子n 3 时输出这 5 种组合((())) (()()) (())() ()(()) ()()()注意这不是排列。n 3 的时候如果纯排列6 个位置里放 3 个左括号和 3 个右括号不考虑合法性一共有 C(6, 3) 20 种。但真正合法输出的只有上面这 5 个。这意味着解法必须从 20 个候选里排除掉 15 个不合法的这就是“筛选”和“剪枝”要干的事。1.2 什么叫“有效括号组合”很多初学者容易忽略一个基础事实判断一段括号串是否合法其实不需要真的去栈里匹配。你只需要从左往右扫描随时保证任意前缀中左括号数量 右括号数量整串结束时左括号数量 右括号数量且均为 n这个结论非常重要。因为如果你用栈去分析每个生成的串那道题的思路就走偏了。这道题的核心不是“验证已经生成的串是否合法”而是“在生成的过程中就保证不制造非法串”。换句话说合法性判断从验证阶段前置到了生成阶段这就是 DFS 回溯的用武之地。我举个例子“())“ 这个串在第二个右括号出现时右括号数量就已经超过了左括号数量所以它不可能合法。而 ”(()“ 虽然前缀没问题但左括号用了 2 个、右括号只用了 1 个总数不到 n 3 的规模所以它只是一个还没完成的中间状态不能算作结果。1.3 为什么你会觉得这道题有难度我自己一开始也卡过后来发现卡住的真正原因不是递归写不出来而是不知道递归函数的参数该怎么设计。你想想看输出的是一个字符串递归的过程中我们在“拼字符串”。拼字符串的过程里我们既要知道已经用了几个左括号又要知道用了几个右括号还得知道当前拼出来的临时串长什么样子——这三个信息缺一个都不行。这是这道题的第一个坎。第二个坎就是终止条件。递归到哪里算结束有人写if (cur.length() 2 * n)有人写if (left n right n)。两种都可以但理解上第二种更贴近“对数”这个含义。我在下文会展开讲这两种写法的细微差别以及为什么我推荐其中一种。第三个坎就是回溯的“状态恢复”。这题如果直接用字符串拼接是天生自带回溯的因为它每次生成新串再传给下一层递归不会污染原来的值。但如果你用 StringBuilder 这类可变结构就必须在递归结束后手动删掉刚才加的字符这一步一旦漏掉输出结果会惨不忍睹。2. 从暴力枚举到 DFS 回溯核心思路的推导过程2.1 暴力解法为什么不行如果完全不懂搜索最原始的想法就是把 2n 个位置看成一排空位每个空位可以放左括号或右括号总共 2^(2n) 种放法然后逐个检查合法性。以 n 4 为例2^(8) 256 种。看起来不多但 n 一旦到了 10就是 2^20 ≈ 104 万种再往上就到了千万、亿级别。而且绝大多数组合在很早的位置就已经非法了你却依然在后面疯狂地枚举。这就像你要在一堆乱七八糟的铁块里找金子明明看一眼就知道这堆铁块方向不对却还是把整堆都翻了个底朝天。暴力解法的时间复杂度是 O(2^(2n) * n)因为每种组合还要花 O(n) 去验证合法性。这个量级面对 n 稍微大一点就直接炸了。2.2 关键启发生成的时候就别让非法情况发生我们再回到合法性标准左括号只要没用完left n就还有资格继续放。右括号只有当right left时才能放因为一旦右括号数量追平甚至超过左括号这个串的前缀合法性就彻底没了。这两条规则就是整棵搜索树的“两个剪枝条件”。请注意剪枝这个词听起来很高端但其实意思特别朴素——这条路我都知道走不通那我还走它干嘛你站在搜索树的一个节点上面前本来有两根分支放左括号、放右括号。有了这两个条件放左括号的分支不总是存在放右括号的分支也不总是存在。这样搜索树就从一棵“满二叉树”被裁剪成了一棵“合法组合专用树”。2.3 用完全二叉树来理解这道题的结构把递归过程想象成在走一棵二叉树根节点是一个空串深度 0每往下一层当前位置就选择放一个左括号或右括号到达第 2n 层时所有选择组合拼起来就是一个完整串截掉那些违反剪枝条件的子树后剩下的每一条“从根到叶子”的路径都是一个合法结果这就是为什么很多题解里说“括号生成本质上是 DFS 遍历一棵隐式二叉树”。隐式的意思是这棵树不是提前建立好的数据结构而是随着递归函数的调用自动展开的。树的总深度是 2n叶子节点数等于合法组合数。我把这个模型说得更具体点每次递归调用都意味着当前节点选择了一个字符函数参数里的cur记录的是“从根到这个节点路径上字符的拼接结果”。走到叶子时cur刚好就是完整的一个括号串。2.4 为什么选择 DFS 而不是 BFS理论上 BFS 一样能做从上到下逐层扩展字符串最后输出所有完整串但 DFS 有三个明显优势递归写法直观代码短容易在面试中手写。DFS 天然配套回溯思想一条路走到黑不行就退回来换条路这和“括号合法性是前缀属性”完美契合。内存开销小BFS 需要维护一整层的中间状态而 DFS 只需要维护当前路径上的临时串。实际做这道题时绝大多数主流题解用的都是 DFS 回溯面试官见到这种解法也最放心。你要是上来写一个 BFS 队列版本也不是不行但解释成本高而且容易在边界条件上绕晕。3. 代码实现详解DFS 回溯的几种写法与核心细节3.1 最推荐的 Python 写法字符串拼接版的隐式回溯Python 里最简洁、最不容易出 Bug 的写法长这样from typing import List class Solution: def generateParenthesis(self, n: int) - List[str]: res [] def dfs(cur: str, left: int, right: int) - None: # 左括号和右括号都已经用完得到一个合法结果 if left n and right n: res.append(cur) return # 剪枝条件1左括号没用完还可以放左括号 if left n: dfs(cur (, left 1, right) # 剪枝条件2右括号数量还没追上左括号数量可以放右括号 if right left: dfs(cur ), left, right 1) dfs(, 0, 0) return res这段代码有几个关键点cur (不会修改cur本身而是生成一个新的字符串传给下层递归。所以根本不需要“撤销”这一步——这就是隐式回溯。left和right分别记录已使用的左右括号数它们也被作为参数传下去下层递归拿到的是一份新的值同样不需要回退。递归终止条件我写成left n and right n而不是len(cur) 2 * n这样更直观语义上也更贴近“n 对括号全部用完”。有人可能会问既然left n and right n能作为终止条件那left n and right left这种状态还存在吗存在而且代码里正是靠“右括号分支的剪枝条件right left”来保证这种情况发生时不会乱放右括号。比如 n 3 时走到(((这个状态后left 3right 0这时候if left n为假左括号分支直接关闭但右括号分支因为0 3依然开放所以还能继续走一直走到((()))。3.2 用 n 2 手动推演一遍递归流程理论说得再多不如手工模拟一次。以 n 2 为例我逐步展开一下调用dfs(, 0, 0)。left0 2走左分支dfs((, 1, 0)。同时检查右分支条件right0 left0不成立所以不放右括号。在dfs((, 1, 0)中left1 2走左分支dfs(((, 2, 0)。右分支条件0 1成立所以也可以走dfs((), 1, 1)。两个分支都会执行。先看左分支dfs(((, 2, 0)left2不再放左括号0 2放右括号得到dfs(((), 2, 1)。接着 1 2再放右括号得到dfs((()), 2, 2)此时 left n and right n把结果(())加入列表返回。再看右分支dfs((), 1, 1)1 2放左括号得到dfs(()(, 2, 1)这个状态再放右括号得到dfs(()(), 2, 2)入结果列表返回。最终结果是[(()), ()()]完全正确。这个过程告诉你一个很重要的规律先递归完左分支再到右分支所以最终 res 里的顺序不是随机排列的而是符合某种深度优先的字典序。这个细节在一些题解里会被忽略但如果你要比较输出顺序和预期是否一致就需要注意它。3.3 Java 写法StringBuilder 需要显式回溯Java 里很多人喜欢用StringBuilder来避免频繁创建字符串这没问题但代价是你必须手动做状态恢复。来看代码import java.util.ArrayList; import java.util.List; class Solution { public ListString generateParenthesis(int n) { ListString res new ArrayList(); backtrack(res, new StringBuilder(), 0, 0, n); return res; } private void backtrack(ListString res, StringBuilder sb, int left, int right, int n) { if (sb.length() 2 * n) { res.add(sb.toString()); return; } if (left n) { sb.append((); backtrack(res, sb, left 1, right, n); sb.deleteCharAt(sb.length() - 1); // 回溯撤销刚才添加的左括号 } if (right left) { sb.append()); backtrack(res, sb, left, right 1, n); sb.deleteCharAt(sb.length() - 1); // 回溯撤销刚才添加的右括号 } } }这里最关键的就是两行sb.deleteCharAt(sb.length() - 1)。为什么必须删因为StringBuilder是一个可变对象你在递归里 append 之后如果返回上层没有删掉刚才加的字符下一轮尝试另一个分支时sb 里就残留了不该有的括号导致结果全部错乱。我在面试时见过不少人在这里翻车。他们记住了要删但删错了位置。正确的位置是递归调用返回后立刻删除。不是递归调用前删也不是递归结束后统一删而是紧跟在backtrack(...)之后。这一点务必牢记。3.4 终止条件与剪枝条件的顺序是否要严格有读者可能注意到了一个细节在我的 Python 版本里终止条件写的是left n and right n而 Java 版本用的是sb.length() 2 * n。两种写法的差别在哪left n and right n语义最清晰只有左右括号都用完才算完整。sb.length() 2 * n判断的是串长度范围更“宽”一些。因为即使左右括号没用完串长度也可能正好是 2n不可能。左右括号数量之和等于串长所以left right 2n和left n right n是等价的。但是sb.length() 2 * n这个条件单独存在时并不保证括号是合法的。它之所以能作为终止条件是因为剪枝条件已经保证了每一步生成的串前缀合法所以串长满 2n 时一定合法。反过来说如果剪枝条件写错了即使用left n right n做终止条件也会输出非法结果。切不要以为终止条件承担了合法性判断的职责合法性主要是靠剪枝条件来守护的。3.5 复杂度分析很多人到这里就直接背答案了时间复杂度 O(4^n / √n)空间复杂度 O(n)。但理解它是怎么来的对后续刷题帮助更大。递归树的深度固定为 2n。合法结果的数量是卡特兰数 C_n C(2n, n) / (n 1)。当 n 4 时是 14n 5 时是 42。搜索过程中实际访问的节点数不会超过卡特兰数乘以一个常数倍所以时间复杂度可以用 O(C_n) 或 O(4^n / √n) 来近似。空间的消耗主要是递归调用栈的深度即 O(2n) O(n)以及StringBuilder或cur字符串本身的长度也是 O(n)。整体空间复杂度就是 O(n)。有人会问如果我用字符串拼接每次递归都会创建新字符串那空间复杂度不是更高吗严格来说每个节点创建一个新字符串确实会让中间字符串的总量变大但因为递归是深度优先的同一时间栈上最多只存在 2n 个字符串副本所以空间复杂度依然是 O(n)。只是常数会比 StringBuilder 版本大一些。日常刷题不会卡这个常数面试也一般不深究但如果你能主动提到这一点会给面试官留下一个“你考虑过性能”的好印象。4. 易错点排查与面试实战经验4.1 四个最常见、最经典的翻车现场我根据自己和身边人刷这道题的实际体验整理了四类高频问题第一类忘记显式回溯状态用StringBuilder、ListCharacter、char[] index这类可变结构时递归调用返回后不deleteCharAt、不remove、不把数组当前位置复位。这是最容易出的错误。第二类右括号剪枝条件写反把if (right left)写成if (right n)。这就等于允许右括号随便放直到放满 n 个为止。结果就是你得到了很多以右括号开头的非法串。这里建议用一个小技巧记忆右括号的“存款”是左括号给的左括号还没用完右括号才能跟上。第三类终止条件写错位置有人喜欢把终止条件放在函数最开头这个没错。但有人会写成if (cur.length() n)这明显不对因为完整串长度是 2n。还有人会漏掉return导致递归不退出栈溢出。别提了都是真实的眼泪。第四类递归函数里把 left/right 参数当成全局变量去修改比如有人写left 1; dfs(...); left - 1;这样倒没问题但如果漏了减回去就变成状态污染了。如果用了 Java 的int参数在递归调用里修改的是本地副本不回溯也没事但如果你把它们放在类的成员变量里那就要格外小心。4.2 面试中常见的追问怎么优化到只生成合法串面试官一般不会满足于看到你写出一版正确代码还会追问一句“你这个算法有没有生成过非法的中间状态能不能做到百分之百不生成非法串”答案就是你用的这个 DFS 回溯从根到叶子全程都遵守两条剪枝规则所以它生成的每一个叶子都是合法的中间路径也没有任何非法前缀。严格来说它并没有先生成非法串再淘汰而是从源头上就没有给非法串任何生存空间。如果把思路换成“先枚举 2^(2n) 种组合再逐个验证”那面试官基本会认为你掉进了暴力陷阱。所以在回答的时候最好主动点破这一点“因为我在每一步保证右括号数不超过左括号数所以整棵搜索树里面没有一个节点代表非法前缀。”4.3 用 LeetCode 的裁判视角理解这个答案你在提交代码时LeetCode 会拿一组标准用例来跑包括 n 1 到 n 8 左右的范围。n 1 的输出是[()]n 0 呢如果题目没特别说明一般 n 是正整数但你还是可以用n 0做个防御性处理返回空列表。不过力扣的原题约束里 n 可以等于 1 开始所以不必太过纠结。我还见过有人问结果顺序要不要按字典序LeetCode 的判定一般是把结果集视为集合不做严格顺序比较。但不同写法的执行顺序不同你在本地测试时输出顺序可能和其他题解不一样这并不代表代码错了。如果你在意那把左分支放在右分支之前自然就是字典序优先的输出。4.4 关于卡特兰数的一个小扩展括号生成的结果数量正好是卡特兰数。卡特兰数还出现在很多组合问题里比如二叉树的形态数、栈的出入栈序列数、多边形三角剖分数等。如果你在面试中答出“这里的结果数量是卡特兰数”其实是加分项因为说明你不只停留在代码层面还看到了它背后的组合数学结构。卡特兰数的递推式是 C_0 1C_n sum(C_i * C_(n-1-i)) for i 0..n-1。这个递推式甚至可以在不知道 DFS 的情况下写出一个 DP 解法。但 DP 解法不适合这道题因为题目要求“列出全部组合”而不是“求组合数量”。如果只要求计数我可能会用 DP 或公式去解但题目要求输出结果DFS 就是最自然的选择。5. 延伸思考回溯模板与同类型题目解法对比5.1 回溯算法的通用骨架括号生成这道题如果剥掉括号的外衣核心就是下面这个模板def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择对应到本题选择列表就是“放左括号”和“放右括号”两个动作但它们不总是同时可用因为受剪枝条件约束。如果把剪枝条件理解为“合规的选择列表”那这个模板和全排列、子集的写法就完全统一了。我看过很多人刷题时用“背模板”的方式复制回溯框架结果遇到这道题还是傻眼因为他们不知道如何把“当前路径上左括号数量”和“右括号数量”映射到模板里的“选择列表”。所以我的建议是背模板可以但一定要知道模板里每个变量在具体题目中代表什么。5.2 与全排列、子集、组合总和的对比这里我做一个对比表帮你看清回溯题的通用性和差异性题目路径含义选择列表剪枝依据括号生成当前拼接的括号串放左括号 / 放右括号left nright left全排列当前排列结果未被使用的剩余数字数字是否已被使用子集当前已选元素集合选当前元素 / 不选不重复选下标组合总和当前已选数字列表按顺序取数字不能回头取相同下标对比下来你会发现回溯题的本质就是“路径 选择列表 剪枝条件”三者组合。括号生成之所以比全排列看起来难一点是因为它的选择列表不是预先给好的一个数组而是由左右括号数量动态生成的。你每做一次选择都会改变下一步可选的选项这个特性在工作中建模时很常见。比如在构建一个层级结构时下一步能选什么往往取决于你当前走到了哪一层。5.3 一个常见困惑递归里的“回溯”到底回溯了什么很多人总觉得“回溯”是一件很玄的事情说要撤销什么。现在用这道题把话说清楚如果你用的是不可变字符串拼接每次调用dfs(cur (, left 1, right)下层拿到的是全新字符串和全新计数上层函数里的cur、left、right根本没变所以下层返回后上层天然回到调用前状态不用显式撤销。如果你用的是StringBuilder这种可变对象你在本层往 sb 里加了一个括号这个修改是“留在原地的”。下层递归基于修改后的 sb 继续拼返回后如果不把 sb 恢复原样后续的其他分支就会基于一个被污染的状态继续搜索。换句话说回溯的本质是“让可变状态在递归返回后和进入时保持一致”。理解了这句话你以后写任何回溯题都会稳很多。5.4 从这道题延伸的开销问题如果需要生成几百万个结果怎么办LeetCode 的测试范围一般 n 不超过 8结果数量也没到爆炸的程度。但如果你在实际项目中遇到类似需求比如要生成 n 15 的括号组合那结果数量会瞬间变成 9694845快一千万条。这时候哪怕 DFS 是“只生成合法串”光存储结果的内存消耗就可能撑爆应用。你需要的就不是简单的列出全部组合而是使用迭代器 / 生成器边生成边消费。或者直接用公式算数量而不是生成具体内容。或者限制输出规模加一个最大条数阈值超过就丢弃。我在代码里会倾向于用生成器写法Python 里就是把res.append换成yielddef generate(n: int): def dfs(cur, left, right): if left n and right n: yield cur return if left n: yield from dfs(cur (, left 1, right) if right left: yield from dfs(cur ), left, right 1) yield from dfs(, 0, 0)这样改的好处是内存里不需要一次性存一个千万级列表调用方可以循环取一个处理一个。这种写法在生产环境里遇到类似“生成所有合理结构”的场景时会非常实用。5.5 后续刷题建议这道题刷透之后我建议按顺序做下面这几道练手题它们全都在吃回溯或者递归树的同一套知识LeetCode 46全排列——考察 used 数组的回溯LeetCode 78子集——考察选或不选的模型LeetCode 39组合总和——考察重复选择与剪枝LeetCode 17电话号码的字母组合——考察多层选择列表的映射LeetCode 301删除无效的括号——是括号生成的高级变体难度高不少适合进阶当你把这几道做完再回头看括号生成会觉得它清爽得不像话。我在实际刷这道题时发现一个通用技巧在递归函数里尽量少用全局变量尽量把状态全部收进参数里。像 left、right、当前字符串都作为参数传下去这样递归天然可复现、可单步调试也不容易有状态污染的隐性问题。如果实在要用类成员变量也要记得它们被多个分支共享每一层修改之后必须负责还原。经验之谈面试时越简单越直白的代码越不容易翻车强行炫技反而可能把自己绕进去。再分享一个我自己调试递归喜欢用的工具在递归函数开头打印一行参数然后在返回前再打印一行。拿 n 2 的例子跑一遍你就能清清楚楚看到 dfs 的进入顺序、完成顺序以及每个分支的剪枝时机。纸上得来终觉浅手写一遍的收获永远比看十遍题解大。 括号生成与DFS回溯：掌握剪枝与递归的核心技巧
刷 LeetCode 的人迟早都会遇到“括号生成”这道题。它在 LeetCode 热题 100 里排得上号面试出现的频率也不低而且它几乎就是为 DFS 回溯量身定做的一道题。很多人一开始看到这道题会被“生成所有合法括号组合”这个描述唬住以为要用什么高深的 DP 或状态机其实本质就是在搜索树上做了一次了不起眼的剪枝。这篇我就把这道题的 DFS 回溯解法从头到尾掰开揉碎地讲清楚包括题目让你在考什么、代码怎么写、为什么这么写、以及我在实际刷题和面试中踩过的坑。这道题适合谁看适合刚接触回溯算法、做过几道二叉树题目但还没怎么写过“搜索类”题目的读者也适合那些已经会用递归但搞不清“回”这个动作到底要回什么的人。如果能把这道题吃透你看全排列、子集、组合总和这些经典回溯题都会顺手很多。因为这道题表面上是在处理括号本质上是在强迫你理解“搜索树的约束条件到底长在哪里”。1. 先看懂题目合法括号组合到底在考什么1.1 题目到底让我们做什么题目给定数字 nn 代表括号的对数。请你生成所有可能的并且有效的括号组合。举个例子n 3 时输出这 5 种组合((())) (()()) (())() ()(()) ()()()注意这不是排列。n 3 的时候如果纯排列6 个位置里放 3 个左括号和 3 个右括号不考虑合法性一共有 C(6, 3) 20 种。但真正合法输出的只有上面这 5 个。这意味着解法必须从 20 个候选里排除掉 15 个不合法的这就是“筛选”和“剪枝”要干的事。1.2 什么叫“有效括号组合”很多初学者容易忽略一个基础事实判断一段括号串是否合法其实不需要真的去栈里匹配。你只需要从左往右扫描随时保证任意前缀中左括号数量 右括号数量整串结束时左括号数量 右括号数量且均为 n这个结论非常重要。因为如果你用栈去分析每个生成的串那道题的思路就走偏了。这道题的核心不是“验证已经生成的串是否合法”而是“在生成的过程中就保证不制造非法串”。换句话说合法性判断从验证阶段前置到了生成阶段这就是 DFS 回溯的用武之地。我举个例子“())“ 这个串在第二个右括号出现时右括号数量就已经超过了左括号数量所以它不可能合法。而 ”(()“ 虽然前缀没问题但左括号用了 2 个、右括号只用了 1 个总数不到 n 3 的规模所以它只是一个还没完成的中间状态不能算作结果。1.3 为什么你会觉得这道题有难度我自己一开始也卡过后来发现卡住的真正原因不是递归写不出来而是不知道递归函数的参数该怎么设计。你想想看输出的是一个字符串递归的过程中我们在“拼字符串”。拼字符串的过程里我们既要知道已经用了几个左括号又要知道用了几个右括号还得知道当前拼出来的临时串长什么样子——这三个信息缺一个都不行。这是这道题的第一个坎。第二个坎就是终止条件。递归到哪里算结束有人写if (cur.length() 2 * n)有人写if (left n right n)。两种都可以但理解上第二种更贴近“对数”这个含义。我在下文会展开讲这两种写法的细微差别以及为什么我推荐其中一种。第三个坎就是回溯的“状态恢复”。这题如果直接用字符串拼接是天生自带回溯的因为它每次生成新串再传给下一层递归不会污染原来的值。但如果你用 StringBuilder 这类可变结构就必须在递归结束后手动删掉刚才加的字符这一步一旦漏掉输出结果会惨不忍睹。2. 从暴力枚举到 DFS 回溯核心思路的推导过程2.1 暴力解法为什么不行如果完全不懂搜索最原始的想法就是把 2n 个位置看成一排空位每个空位可以放左括号或右括号总共 2^(2n) 种放法然后逐个检查合法性。以 n 4 为例2^(8) 256 种。看起来不多但 n 一旦到了 10就是 2^20 ≈ 104 万种再往上就到了千万、亿级别。而且绝大多数组合在很早的位置就已经非法了你却依然在后面疯狂地枚举。这就像你要在一堆乱七八糟的铁块里找金子明明看一眼就知道这堆铁块方向不对却还是把整堆都翻了个底朝天。暴力解法的时间复杂度是 O(2^(2n) * n)因为每种组合还要花 O(n) 去验证合法性。这个量级面对 n 稍微大一点就直接炸了。2.2 关键启发生成的时候就别让非法情况发生我们再回到合法性标准左括号只要没用完left n就还有资格继续放。右括号只有当right left时才能放因为一旦右括号数量追平甚至超过左括号这个串的前缀合法性就彻底没了。这两条规则就是整棵搜索树的“两个剪枝条件”。请注意剪枝这个词听起来很高端但其实意思特别朴素——这条路我都知道走不通那我还走它干嘛你站在搜索树的一个节点上面前本来有两根分支放左括号、放右括号。有了这两个条件放左括号的分支不总是存在放右括号的分支也不总是存在。这样搜索树就从一棵“满二叉树”被裁剪成了一棵“合法组合专用树”。2.3 用完全二叉树来理解这道题的结构把递归过程想象成在走一棵二叉树根节点是一个空串深度 0每往下一层当前位置就选择放一个左括号或右括号到达第 2n 层时所有选择组合拼起来就是一个完整串截掉那些违反剪枝条件的子树后剩下的每一条“从根到叶子”的路径都是一个合法结果这就是为什么很多题解里说“括号生成本质上是 DFS 遍历一棵隐式二叉树”。隐式的意思是这棵树不是提前建立好的数据结构而是随着递归函数的调用自动展开的。树的总深度是 2n叶子节点数等于合法组合数。我把这个模型说得更具体点每次递归调用都意味着当前节点选择了一个字符函数参数里的cur记录的是“从根到这个节点路径上字符的拼接结果”。走到叶子时cur刚好就是完整的一个括号串。2.4 为什么选择 DFS 而不是 BFS理论上 BFS 一样能做从上到下逐层扩展字符串最后输出所有完整串但 DFS 有三个明显优势递归写法直观代码短容易在面试中手写。DFS 天然配套回溯思想一条路走到黑不行就退回来换条路这和“括号合法性是前缀属性”完美契合。内存开销小BFS 需要维护一整层的中间状态而 DFS 只需要维护当前路径上的临时串。实际做这道题时绝大多数主流题解用的都是 DFS 回溯面试官见到这种解法也最放心。你要是上来写一个 BFS 队列版本也不是不行但解释成本高而且容易在边界条件上绕晕。3. 代码实现详解DFS 回溯的几种写法与核心细节3.1 最推荐的 Python 写法字符串拼接版的隐式回溯Python 里最简洁、最不容易出 Bug 的写法长这样from typing import List class Solution: def generateParenthesis(self, n: int) - List[str]: res [] def dfs(cur: str, left: int, right: int) - None: # 左括号和右括号都已经用完得到一个合法结果 if left n and right n: res.append(cur) return # 剪枝条件1左括号没用完还可以放左括号 if left n: dfs(cur (, left 1, right) # 剪枝条件2右括号数量还没追上左括号数量可以放右括号 if right left: dfs(cur ), left, right 1) dfs(, 0, 0) return res这段代码有几个关键点cur (不会修改cur本身而是生成一个新的字符串传给下层递归。所以根本不需要“撤销”这一步——这就是隐式回溯。left和right分别记录已使用的左右括号数它们也被作为参数传下去下层递归拿到的是一份新的值同样不需要回退。递归终止条件我写成left n and right n而不是len(cur) 2 * n这样更直观语义上也更贴近“n 对括号全部用完”。有人可能会问既然left n and right n能作为终止条件那left n and right left这种状态还存在吗存在而且代码里正是靠“右括号分支的剪枝条件right left”来保证这种情况发生时不会乱放右括号。比如 n 3 时走到(((这个状态后left 3right 0这时候if left n为假左括号分支直接关闭但右括号分支因为0 3依然开放所以还能继续走一直走到((()))。3.2 用 n 2 手动推演一遍递归流程理论说得再多不如手工模拟一次。以 n 2 为例我逐步展开一下调用dfs(, 0, 0)。left0 2走左分支dfs((, 1, 0)。同时检查右分支条件right0 left0不成立所以不放右括号。在dfs((, 1, 0)中left1 2走左分支dfs(((, 2, 0)。右分支条件0 1成立所以也可以走dfs((), 1, 1)。两个分支都会执行。先看左分支dfs(((, 2, 0)left2不再放左括号0 2放右括号得到dfs(((), 2, 1)。接着 1 2再放右括号得到dfs((()), 2, 2)此时 left n and right n把结果(())加入列表返回。再看右分支dfs((), 1, 1)1 2放左括号得到dfs(()(, 2, 1)这个状态再放右括号得到dfs(()(), 2, 2)入结果列表返回。最终结果是[(()), ()()]完全正确。这个过程告诉你一个很重要的规律先递归完左分支再到右分支所以最终 res 里的顺序不是随机排列的而是符合某种深度优先的字典序。这个细节在一些题解里会被忽略但如果你要比较输出顺序和预期是否一致就需要注意它。3.3 Java 写法StringBuilder 需要显式回溯Java 里很多人喜欢用StringBuilder来避免频繁创建字符串这没问题但代价是你必须手动做状态恢复。来看代码import java.util.ArrayList; import java.util.List; class Solution { public ListString generateParenthesis(int n) { ListString res new ArrayList(); backtrack(res, new StringBuilder(), 0, 0, n); return res; } private void backtrack(ListString res, StringBuilder sb, int left, int right, int n) { if (sb.length() 2 * n) { res.add(sb.toString()); return; } if (left n) { sb.append((); backtrack(res, sb, left 1, right, n); sb.deleteCharAt(sb.length() - 1); // 回溯撤销刚才添加的左括号 } if (right left) { sb.append()); backtrack(res, sb, left, right 1, n); sb.deleteCharAt(sb.length() - 1); // 回溯撤销刚才添加的右括号 } } }这里最关键的就是两行sb.deleteCharAt(sb.length() - 1)。为什么必须删因为StringBuilder是一个可变对象你在递归里 append 之后如果返回上层没有删掉刚才加的字符下一轮尝试另一个分支时sb 里就残留了不该有的括号导致结果全部错乱。我在面试时见过不少人在这里翻车。他们记住了要删但删错了位置。正确的位置是递归调用返回后立刻删除。不是递归调用前删也不是递归结束后统一删而是紧跟在backtrack(...)之后。这一点务必牢记。3.4 终止条件与剪枝条件的顺序是否要严格有读者可能注意到了一个细节在我的 Python 版本里终止条件写的是left n and right n而 Java 版本用的是sb.length() 2 * n。两种写法的差别在哪left n and right n语义最清晰只有左右括号都用完才算完整。sb.length() 2 * n判断的是串长度范围更“宽”一些。因为即使左右括号没用完串长度也可能正好是 2n不可能。左右括号数量之和等于串长所以left right 2n和left n right n是等价的。但是sb.length() 2 * n这个条件单独存在时并不保证括号是合法的。它之所以能作为终止条件是因为剪枝条件已经保证了每一步生成的串前缀合法所以串长满 2n 时一定合法。反过来说如果剪枝条件写错了即使用left n right n做终止条件也会输出非法结果。切不要以为终止条件承担了合法性判断的职责合法性主要是靠剪枝条件来守护的。3.5 复杂度分析很多人到这里就直接背答案了时间复杂度 O(4^n / √n)空间复杂度 O(n)。但理解它是怎么来的对后续刷题帮助更大。递归树的深度固定为 2n。合法结果的数量是卡特兰数 C_n C(2n, n) / (n 1)。当 n 4 时是 14n 5 时是 42。搜索过程中实际访问的节点数不会超过卡特兰数乘以一个常数倍所以时间复杂度可以用 O(C_n) 或 O(4^n / √n) 来近似。空间的消耗主要是递归调用栈的深度即 O(2n) O(n)以及StringBuilder或cur字符串本身的长度也是 O(n)。整体空间复杂度就是 O(n)。有人会问如果我用字符串拼接每次递归都会创建新字符串那空间复杂度不是更高吗严格来说每个节点创建一个新字符串确实会让中间字符串的总量变大但因为递归是深度优先的同一时间栈上最多只存在 2n 个字符串副本所以空间复杂度依然是 O(n)。只是常数会比 StringBuilder 版本大一些。日常刷题不会卡这个常数面试也一般不深究但如果你能主动提到这一点会给面试官留下一个“你考虑过性能”的好印象。4. 易错点排查与面试实战经验4.1 四个最常见、最经典的翻车现场我根据自己和身边人刷这道题的实际体验整理了四类高频问题第一类忘记显式回溯状态用StringBuilder、ListCharacter、char[] index这类可变结构时递归调用返回后不deleteCharAt、不remove、不把数组当前位置复位。这是最容易出的错误。第二类右括号剪枝条件写反把if (right left)写成if (right n)。这就等于允许右括号随便放直到放满 n 个为止。结果就是你得到了很多以右括号开头的非法串。这里建议用一个小技巧记忆右括号的“存款”是左括号给的左括号还没用完右括号才能跟上。第三类终止条件写错位置有人喜欢把终止条件放在函数最开头这个没错。但有人会写成if (cur.length() n)这明显不对因为完整串长度是 2n。还有人会漏掉return导致递归不退出栈溢出。别提了都是真实的眼泪。第四类递归函数里把 left/right 参数当成全局变量去修改比如有人写left 1; dfs(...); left - 1;这样倒没问题但如果漏了减回去就变成状态污染了。如果用了 Java 的int参数在递归调用里修改的是本地副本不回溯也没事但如果你把它们放在类的成员变量里那就要格外小心。4.2 面试中常见的追问怎么优化到只生成合法串面试官一般不会满足于看到你写出一版正确代码还会追问一句“你这个算法有没有生成过非法的中间状态能不能做到百分之百不生成非法串”答案就是你用的这个 DFS 回溯从根到叶子全程都遵守两条剪枝规则所以它生成的每一个叶子都是合法的中间路径也没有任何非法前缀。严格来说它并没有先生成非法串再淘汰而是从源头上就没有给非法串任何生存空间。如果把思路换成“先枚举 2^(2n) 种组合再逐个验证”那面试官基本会认为你掉进了暴力陷阱。所以在回答的时候最好主动点破这一点“因为我在每一步保证右括号数不超过左括号数所以整棵搜索树里面没有一个节点代表非法前缀。”4.3 用 LeetCode 的裁判视角理解这个答案你在提交代码时LeetCode 会拿一组标准用例来跑包括 n 1 到 n 8 左右的范围。n 1 的输出是[()]n 0 呢如果题目没特别说明一般 n 是正整数但你还是可以用n 0做个防御性处理返回空列表。不过力扣的原题约束里 n 可以等于 1 开始所以不必太过纠结。我还见过有人问结果顺序要不要按字典序LeetCode 的判定一般是把结果集视为集合不做严格顺序比较。但不同写法的执行顺序不同你在本地测试时输出顺序可能和其他题解不一样这并不代表代码错了。如果你在意那把左分支放在右分支之前自然就是字典序优先的输出。4.4 关于卡特兰数的一个小扩展括号生成的结果数量正好是卡特兰数。卡特兰数还出现在很多组合问题里比如二叉树的形态数、栈的出入栈序列数、多边形三角剖分数等。如果你在面试中答出“这里的结果数量是卡特兰数”其实是加分项因为说明你不只停留在代码层面还看到了它背后的组合数学结构。卡特兰数的递推式是 C_0 1C_n sum(C_i * C_(n-1-i)) for i 0..n-1。这个递推式甚至可以在不知道 DFS 的情况下写出一个 DP 解法。但 DP 解法不适合这道题因为题目要求“列出全部组合”而不是“求组合数量”。如果只要求计数我可能会用 DP 或公式去解但题目要求输出结果DFS 就是最自然的选择。5. 延伸思考回溯模板与同类型题目解法对比5.1 回溯算法的通用骨架括号生成这道题如果剥掉括号的外衣核心就是下面这个模板def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择对应到本题选择列表就是“放左括号”和“放右括号”两个动作但它们不总是同时可用因为受剪枝条件约束。如果把剪枝条件理解为“合规的选择列表”那这个模板和全排列、子集的写法就完全统一了。我看过很多人刷题时用“背模板”的方式复制回溯框架结果遇到这道题还是傻眼因为他们不知道如何把“当前路径上左括号数量”和“右括号数量”映射到模板里的“选择列表”。所以我的建议是背模板可以但一定要知道模板里每个变量在具体题目中代表什么。5.2 与全排列、子集、组合总和的对比这里我做一个对比表帮你看清回溯题的通用性和差异性题目路径含义选择列表剪枝依据括号生成当前拼接的括号串放左括号 / 放右括号left nright left全排列当前排列结果未被使用的剩余数字数字是否已被使用子集当前已选元素集合选当前元素 / 不选不重复选下标组合总和当前已选数字列表按顺序取数字不能回头取相同下标对比下来你会发现回溯题的本质就是“路径 选择列表 剪枝条件”三者组合。括号生成之所以比全排列看起来难一点是因为它的选择列表不是预先给好的一个数组而是由左右括号数量动态生成的。你每做一次选择都会改变下一步可选的选项这个特性在工作中建模时很常见。比如在构建一个层级结构时下一步能选什么往往取决于你当前走到了哪一层。5.3 一个常见困惑递归里的“回溯”到底回溯了什么很多人总觉得“回溯”是一件很玄的事情说要撤销什么。现在用这道题把话说清楚如果你用的是不可变字符串拼接每次调用dfs(cur (, left 1, right)下层拿到的是全新字符串和全新计数上层函数里的cur、left、right根本没变所以下层返回后上层天然回到调用前状态不用显式撤销。如果你用的是StringBuilder这种可变对象你在本层往 sb 里加了一个括号这个修改是“留在原地的”。下层递归基于修改后的 sb 继续拼返回后如果不把 sb 恢复原样后续的其他分支就会基于一个被污染的状态继续搜索。换句话说回溯的本质是“让可变状态在递归返回后和进入时保持一致”。理解了这句话你以后写任何回溯题都会稳很多。5.4 从这道题延伸的开销问题如果需要生成几百万个结果怎么办LeetCode 的测试范围一般 n 不超过 8结果数量也没到爆炸的程度。但如果你在实际项目中遇到类似需求比如要生成 n 15 的括号组合那结果数量会瞬间变成 9694845快一千万条。这时候哪怕 DFS 是“只生成合法串”光存储结果的内存消耗就可能撑爆应用。你需要的就不是简单的列出全部组合而是使用迭代器 / 生成器边生成边消费。或者直接用公式算数量而不是生成具体内容。或者限制输出规模加一个最大条数阈值超过就丢弃。我在代码里会倾向于用生成器写法Python 里就是把res.append换成yielddef generate(n: int): def dfs(cur, left, right): if left n and right n: yield cur return if left n: yield from dfs(cur (, left 1, right) if right left: yield from dfs(cur ), left, right 1) yield from dfs(, 0, 0)这样改的好处是内存里不需要一次性存一个千万级列表调用方可以循环取一个处理一个。这种写法在生产环境里遇到类似“生成所有合理结构”的场景时会非常实用。5.5 后续刷题建议这道题刷透之后我建议按顺序做下面这几道练手题它们全都在吃回溯或者递归树的同一套知识LeetCode 46全排列——考察 used 数组的回溯LeetCode 78子集——考察选或不选的模型LeetCode 39组合总和——考察重复选择与剪枝LeetCode 17电话号码的字母组合——考察多层选择列表的映射LeetCode 301删除无效的括号——是括号生成的高级变体难度高不少适合进阶当你把这几道做完再回头看括号生成会觉得它清爽得不像话。我在实际刷这道题时发现一个通用技巧在递归函数里尽量少用全局变量尽量把状态全部收进参数里。像 left、right、当前字符串都作为参数传下去这样递归天然可复现、可单步调试也不容易有状态污染的隐性问题。如果实在要用类成员变量也要记得它们被多个分支共享每一层修改之后必须负责还原。经验之谈面试时越简单越直白的代码越不容易翻车强行炫技反而可能把自己绕进去。再分享一个我自己调试递归喜欢用的工具在递归函数开头打印一行参数然后在返回前再打印一行。拿 n 2 的例子跑一遍你就能清清楚楚看到 dfs 的进入顺序、完成顺序以及每个分支的剪枝时机。纸上得来终觉浅手写一遍的收获永远比看十遍题解大。