1. 这道题到底在考什么从括号看穿树形决策的本质LeetCode 22 号题括号生成我刷了三遍才真正觉得自己会了。第一遍背代码第二遍看懂第三遍才敢说理解。这东西表面是字符串题面试官真正想看的是你有没有把生成过程抽象成决策过程的能力。先看题目本身给定 n 代表括号的对数生成所有可能的并且有效的括号组合。n3 时输出应该是这五组((())) (()()) (())() ()(()) ()()()注意排序不重要重要的是所有和有效两个词。很多人第一反应是括号就左右两种一共 2n 个位置每个位置要么左要么右直接枚举不就行了理论上没错但 n3 时就有 2^664 种组合最终只有 5 种合法大部分时间都在做无用功。这道题真正考察的模型是一个带约束的树形决策。你可以把 2n 个位置看成一条从根到叶子的路径每一步有两个选择放左括号还是右括号。问题从枚举所有字符串变成在决策树上走出一条满足约束条件的路径后者正是回溯算法Backtracking的典型应用场景。为什么我说它是模型而不是字符串题因为同样的决策结构换一层皮就是其他题n 对括号对应 n 次入栈出栈、二叉树的 n 个节点形态数量、矩阵连乘的加括号方式……理解了这个模型你刷的就不只是一道题而是一类题。对基础不同的读者我的建议是如果你是第一次接触回溯先把本文第 3 节剪枝条件的推导看懂如果你已经会做了直接跳到第 6 节和第 7 节那部分是我反复踩坑后的经验总结。2. 先从最笨的方法说起暴力枚举的完整推导与它的致命短板2.1 暴力法怎么写所有组合 逐条验证暴力法思路很直白先生成所有可能的长度为 2n 的括号串再筛出合法的。生成所有组合可以用递归也可以用一个简单的二进制掩码思路——每个位置两种选择总共 2^(2n) 种比如 n3 就是 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)验证开销约合法结果数卡特兰数364384551,0245,12042865,536524,2881,430101,048,57610,485,76016,796151,073,741,82416,109,127,3609,694,845n15 时已经要枚举 10 亿个字符串哪怕每微秒处理一个也要十几分钟。而合法结果只有 969 万。换句话说大量时间花在了注定无效的序列上。2.3 暴力法的真正价值当基准不当事后笑话我不会否认暴力法的价值。写算法题时我的习惯是先暴力再优化。暴力解法代码短、逻辑简单尤其适合做测试基准——回溯解法写完拿 n3、n4 和暴力结果对拍能立刻确认剪枝逻辑没有漏掉答案。另一个价值是帮助理解为什么需要剪枝。当我第一次画出 n3 的暴力递归树再画出剪枝后的递归树才真正明白剪枝省掉的不是一两个节点而是一整片一整片的无效子树。3. 回溯剪枝的两个条件是怎么来的递归树的形态与边界判断3.1 两个剪枝条件的完整推导回溯相比暴力的核心区别在于**等发现路径无效再回头不如在每一步就判断这条路值不值得走下去。**放到括号生成里就是递归进入下一层之前就检查两个条件。条件一还能放左括号吗如果已经用了 open 个左括号只要 open n就可以继续放(。因为每对括号需要一个左括号n 对就需要 n 个左括号没到 n 个就能放。条件二还能放右括号吗如果已经用了 close 个右括号只有 close open 时才可以放)。因为右括号不能比左括号多——否则当前前缀必然无法成为合法序列。这两个条件哪个可以省理论上都不能省。你可以试试只剪条件一不剪条件二当 open 已经等于 n还能继续放右括号最终会生成什么((()))之后又出现(()))这种整个串长度都是 2n1 的东西直接越界。反过来只剪条件二不剪条件一会一直放左括号直到放无可放右括号又因为 close open 一直有机会补最终生成一个 balance 恒非负的合法串——但 open 超过 n 意味着左括号数量大于右括号balance 为 0 时序列长度超过 2n结果还是错的。正确的组合是右括号受左括号数量约束左括号受 n 约束两者缺一不可。3.2 递归树的形态剪枝到底砍掉了什么我用 n2 画一个决策树的文字版帮助你理解剪枝前后的差异。暴力枚举的树 / \ ( ) / \ / \ ( ) ( ) / \ / \ / \ / \ ( )...共 16 个叶子剪枝后的树 / ( / \ ( ) / \ ( ) / ) / )看到区别了吗第一个节点就只剩一个分支了因为初始时 close0、open0第二个条件close open是 0 0不成立所以)从一开始就被否决。这直观说明第一个字符永远是(因为任何合法括号串第一个字符不可能是右括号。剪枝条件在不知不觉中就把这些显而易见的无效路径全都排除了。递归树每一层的节点状态可以表示成(open, close)二元组。根是 (0,0)每放一个左括号 open1每放一个右括号 close1。剪枝规则翻译成状态转移就是从 (open, close) 可以转移到 (open1, close)当且仅当 open n可以转移到 (open, close1)当且仅当 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 ListString generateParenthesis(int n) { ListString res new ArrayList(); dfs(res, new StringBuilder(), 0, 0, n); return res; } private void dfs(ListString 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 resPython 里path用 listpop()负责撤销.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 最大到 8String 版也能过但面试时如果 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 ListString generateParenthesis(int n) { ListListString dp new ArrayList(); dp.add(List.of()); // 0 对括号 for (int i 1; i n; i) { ListString 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 / (n1)) * C(2n, n) (2n)! / ((n1)! * n!)n3 时 C_3 (1/4) * 20 5正好对上n4 时 14n5 时 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 亲身验证n10 时的体感我实际跑过 n10回溯版耗时几十毫秒暴力版要跑几十秒。n 再大一档暴力版基本没法用了。这个体感差异比任何复杂度公式都来得直观。在面试或者实际项目中你永远应该选择尽可能早地砍掉不可能的分支这种思路。6. 从会做到写对易错点、边界条件与调试技巧6.1 五个高频翻车点第一个忘掉撤销。StringBuilder 或 list 路径不 pop导致兄弟分支串味。这是最长见的错误没有之一。第二个剪枝条件方向写反。有人写成if (close open)然后递归全部乱套。写成close open才对语义是只有右括号还不够的时候才补充右括号。第三个终止条件写成len n或者open n。前者提前结束只生成长度为 n 的序列后者少了 close 也达到 n 的检查会在 close 超限后继续递归。第四个n0 时返回什么。[,]还是[]题目明确 n 是正整数的话不用管但有些变体题会问 n0那时候要约定返回[]空字符串代表零对括号的一种组合而不是空列表。第五个对res.add(sb.toString())的位置理解不到位。必须在叶子处 add。如果放在(open n)分支内部会提前把不完整的序列存下来结果全是半成品。6.2 边界用例一览输入期望输出说明n0[]部分题设空串也是一对都没有的唯一组合n1[()]唯一合法组合n2[(()), ()()]两种合法组合n35 种教材级用例n81,430 种LeetCode 默认上限6.3 调试技巧打印递归树状态我第一次写回溯时总是不确定剪枝对不对后来学会一招递归入口打印当前 open、close、path。n2 时的输出大致是open0 close0 path open1 close0 path( open2 close0 path(( open2 close1 path(() open2 close2 path(()) open1 close1 path() open2 close1 path()( open2 close2 path()()看一眼递归路径立刻就能发现哪些分支被剪掉了哪些走重了。对新手来说这个可视化的价值比任何注释都大。6.4 如何向面试官解释你的代码我复盘自己面试时发现一个好的口头表述是:我把这个过程看成走迷宫每一步要么放左括号要么放右括号但放右括号之前必须确认当前右括号的数量还没追上左括号。当左右括号都用完时当前路径就是一个合法解。然后撤销这一步的选择继续尝试另一个方向。 这个说法既描述了回溯的本质又说明了剪枝依据面试官通常能直接 get 到你的思路。7. 这道题不是一个孤岛括号类题型的血缘关系与迁移价值7.1 括号家族的题谱括号生成的思路能直接迁移到好几道 LeetCode 题上LeetCode 20 有效括号给一个字符串判断是否合法用栈或计数器是第 2 节验证逻辑的直接应用。LeetCode 32 最长有效括号求最长的合法括号子串需要 DP 或栈难度直接上一个台阶。LeetCode 301 删除无效的括号给定含非法括号的字符串删掉最少的字符使其合法返回所有结果。这道题本质上是反向生成先统计需要删除的左右括号数量再带着计数做回溯。LeetCode 678 有效的括号字符串带*通配符的变体用双栈或 DP。做完括号生成后再做这几道你会发现自己对各种括号约束的敏感度高了很多。7.2 卡特兰数的其他等价形态括号组合的数量和下面这些经典问题的答案数学上是同一个数n 个元素的出栈序列数量n 个节点能构成的不同二叉树的形态数凸 n2 边形的三角形划分方法数从 (0,0) 到 (n,n) 不越过对角线的路径数。知道这层联系有什么用面试如果深挖你可以通过括号生成引出卡特兰数这个话题展示知识广度。我从个人经验说这种关联思维在算法轮非常加分因为大部分候选人只会背模板。7.3 把括号生成的思路用到别的组合搜索题括号生成是典型的约束组合搜索问题。同一类套路可以迁移到全排列需要一个 used 数组避免重复使用同一元素组合总和排序 剪枝N 皇后判断列、对角线是否冲突子集每个元素选或不选。这些题共用的框架都是递归 路径 撤销差别只在于约束条件怎么定义。括号生成恰好是约束条件最简单、最直观的那一道所以非常适合作为回溯入门的敲门砖。一旦你彻底吃透了它后面遇到 n 皇后、解数独这类复杂约束题至少不会害怕。7.4 我个人的一点建议刷题不是刷数量是刷模型的连接。括号生成这道题我建议你至少做三遍第一遍照着答案写第二遍不看答案独立写第三遍隔两周回来用另一种解法动态规划再写一遍。第三遍的时候你会发现原来背的代码已经断了能用语言清晰地讲出自己的思路那才是真会了。尝试用这道题去串起整个括号家族再去串起回溯算法这个大框架。刷题到后期你手里握的不是一道一道孤立的题而是一张互相连接的网——括号生成就是这张网里非常值得锚定的一个节点。