括号生成这道题在力扣热题100里排到第59位题面很短给定 n返回所有 n 对括号组成的合法组合。我第一次刷的时候第一反应是生成所有括号串再逐个判断后来看到别人的回溯代码只有十几行心想这不就是全排列加剪枝吗。但等到面试现场被追问了一句“为什么剪枝条件是close open”时我才发现自己只是把代码默写出来了。这篇文章想把回溯和按括号序列长度递归也就是常说的 DP 递推都拆一遍重点放在两类解法的推导过程、复杂度账本以及实际提交里最容易翻车的细节。1. 题目到底在问什么合法括号串的两个硬约束1.1 输入输出先看明白输入是一个整数 n表示括号的“对数”不是“个数”。n 3 时输出 5 个结果((())) (()()) (())() ()(()) ()()()注意这里每一对括号都是小括号()不存在方括号、花括号混用。题目要求的是“所有可能且合法”的组合返回顺序无所谓判题系统不会因为顺序不同就判错。之前见过有人把((()))写成了(()())的重复变体其实这两个是不同的序列一个嵌套两层一个是一层嵌套加一层并列。长度为固定值2 * n每个字符只能是(或)。这是后续所有解法能展开的基础候选字符只有两种所以天生适合用决策树去描述。1.2 合法性判断左右数量相等和任意前缀不能出现右多于左判断一个括号串是否合法很多人第一反应是“左右括号数量相等”。这确实是一个必要条件但远远不够。比如())(()左右都是三个括号可它显然是错的第三个字符处右括号就把左括号给消超了。严格来说有两个条件整个串里左括号数 右括号数 n。从串的任意位置往前截取一段前缀左括号出现次数必须不小于右括号出现次数。第二个条件可以类比成一个栈遇到(就压栈遇到)就弹栈。合法序列的任何一个瞬间都不能对空栈做弹栈操作。所以任意前缀中左括号数量一旦小于右括号数量这个括号串就废了。对应的判断代码一般长这样def is_valid(s: str) - bool: bal 0 for ch in s: if ch (: bal 1 else: bal - 1 if bal 0: return False return bal 0先有这个判断函数再去理解后面的剪枝条件会轻松很多。回溯和 DP 做的事情本质上就是把这两条硬约束前置到“生成过程”里而不是先生成完再回头检查。1.3 暴力生成再筛选为什么不是首选解法最朴素的做法枚举长度为2n的所有字符串然后用is_valid过滤。以 n 3 为例总共有2^6 64个候选串合法的是 5 个绝大多数都在白白生成。n 8 时总候选串2^16 65536合法结果是 1430 个这个数据规模其实还能跑。但 n 12 时候选串变成 1600 万n 15 时超过 10 亿暴力法就开始吃力了。换句话说暴力法在小数据下“能过”但它并不是这道题期望的思路。原因有两个大量无效状态被生成后才被丢弃浪费在凑数量上如果题目升级成“求第 k 个合法序列”或者“统计数量”暴力枚举完全没法复用。所以我们要做的不是在广度上枚举而是在生成过程中提前砍掉非法分支这就是回溯。又或者从结构上做组合拆分这就引出了按序列长度递归的 DP 解法。2. 回溯法把选择过程画成一棵决策树2.1 决策树模型每一步只做一件事在当前字符串后面追加一个(或者)。于是整个过程就是一棵深度为2n的二叉树每个节点代表当前已经生成的前缀。如果完全没有剪枝那么叶子数量是2^(2n)。但我们知道空串的时候不能直接加)因为那样第一轮就违反了“任意前缀左括号数不小于右括号数”。同理任何时刻右括号数量已经等于左括号数量时也不能再加右括号。所以回溯的状态需要维护三个信息path当前已经拼好的前缀open已经使用了多少个左括号close已经使用了多少个右括号。两个剪枝条件也顺势得出只有open n时才允许再加一个左括号只有close open时才允许再加一个右括号。用通俗的话说左括号只要没放到上限就能继续放右括号只能在右括号数量被左括号“压住”的情况下放。2.2 回溯模板代码Python 里比较推荐的写法是用 list 保存路径递归前 push递归后 pop。from typing import List class Solution: def generateParenthesis(self, n: int) - List[str]: res [] path [] def dfs(open_cnt: int, close_cnt: int) - None: # 左右括号都用完了当前 path 就是一组合法结果 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代码里每个if分支前都有合法性判断递归出口处不再需要调用is_valid因为从根到叶子的每一条路径都始终是合法前缀。也许有朋友会问为什么先写open_cnt n再写close_cnt open_cnt顺序其实不影响最终正确性只是先尝试左括号会让结果按“嵌套优先”的方式生成讲思路时也更好表达。力扣判题不依赖输出顺序所以这个顺序完全是你自己的偏好。2.3 n2 的完整执行过程只讲模板不跑例子新手还是容易晕。我们一步步过一遍n 2dfs(, 0, 0) ├─ dfs((, 1, 0) │ ├─ dfs(((, 2, 0) │ │ └─ dfs(((), 2, 1) │ │ └─ dfs((()), 2, 2) - 记录 (()) │ └─ dfs((), 1, 1) │ ├─ dfs(()(, 2, 1) │ │ └─ dfs(()(), 2, 2) - 记录 ()() │ └─ 这里 close1, open1close open 不成立不能加右括号关键节点在于dfs((), 1, 1)。此时左括号数和右括号数相等如果再加右括号就会得到())前缀处右括号超过左括号非法。剪枝在这里生效。同时注意从((,1,0)出发第一个分支(((,2,0)之后因为open_cnt n不能再加左括号只能加右括号所以会一路往右形成(())。第二个分支就是先闭合第一对括号再生成后面的()形成()()。这两种情况正好把 n2 的两类结构都覆盖了。2.4 为什么不需要最后再检查合法性有读者可能不放心万一最后open n and close n但中间出现过非法状态呢答案是不会因为两条剪枝约束已经保证路径上每一步都是合法前缀。我们用数学归纳法理解一下初始状态是空串右括号数为 0左括号数为 0显然合法每次加左括号时左括号数加一前缀左括号始终不小于右括号每次加右括号时前提是当前右括号数小于左括号数加完后右括号数仍然不超过左括号数。到最后open close n前缀条件也满足两点合起来就是合法括号序列。所以出口处只需要判断数量用满不用再写一层校验。3. 按序列长度递归从(A)B的嵌套结构推公式3.1 关键观察第一个左括号必然有配对右括号回溯是从过程出发按长度递归则是从“最终结果长什么样”出发。任何一个非空的合法括号序列它的第一个字符必然是(。这个左括号一定会和后面某个位置的右括号配对而且配对位置是唯一确定的。假设这个配对的右括号是第 k 位那么整个序列可以拆成三部分( A ) B其中 A 是被这对括号包裹的内部内容B 是这对括号右侧的剩余内容。由于括号匹配的本质是栈结构A 和 B 两者本身也必须各自是合法括号序列。举个例子(())拆成(() )更准确地说(())里第一个左括号与最后一个右括号配对所以 A ()B 空串()()里第一个左括号与第二个字符的右括号配对所以 A 空串B ()。这个拆分是唯一的不存在同一个序列被拆成两种不同 A、B 的可能。这是按长度递归能够不重不漏的数学基础。3.2 递推公式与gen(0)边界记gen(k)表示生成 k 对括号的所有合法序列。空括号序列是合法的所以gen(0) []对k 0枚举最外层配对内部包含的括号对数i那么配对右侧还剩k - 1 - i对括号。于是gen(k) { ( a ) b | i 属于 [0, k-1], a 属于 gen(i), b 属于 gen(k-1-i) }i 的取值范围是 0 到 k-1因为最外层已经用掉一对括号内部和右侧合计只有 k-1 对。这个递推式其实就是卡特兰数的经典公式。试着手算gen(2)i0: 取 a b gen(1) 里的()得到()()i1: 取 a ()b gen(0) 里的得到(())。结果是两个符合预期。手算gen(3)也能得到五个正好是卡特兰数 C3。3.3 代码实现递归版这里的“按括号序列长度递归”本质上就是按括号对数 k 从小到大递归。用 Python 加一个记忆化缓存可以避免同一个 k 被重复展开多次。from typing import List class Solution: def generateParenthesis(self, n: int) - List[str]: cache {} def gen(k: int) - List[str]: if k 0: return [] if k in cache: return cache[k] res [] for i in range(k): for a in gen(i): # 内部i 对括号 for b in gen(k - 1 - i): # 右侧k-1-i 对括号 res.append(( a ) b) cache[k] res return res return gen(n)代码非常短。核心就是双层循环第一层枚举内部括号对数第二层把左右两侧的合法子序列拼起来。记忆化保证了每个 k 只计算一次否则这个递归会做大量重复计算。3.4 自底向上DP写法以及为什么不会重复如果你更喜欢标准 DP 写法可以从 0 向上推class Solution: def generateParenthesis(self, n: int) - List[str]: dp [[] for _ in range(n 1)] dp[0] [] for k in range(1, n 1): for i in range(k): for a in dp[i]: for b in dp[k - 1 - i]: dp[k].append(( a ) b) return dp[n]自底向上的好处是不需要写递归不容易把栈溢出挂在心上。缺点是它会老老实实保存从dp[0]到dp[n-1]的所有结果因为构造dp[k]时需要引用它们中间结果不能提前释放。前面已经提到任取一个合法序列第一个左括号的配对位置是唯一的所以(A)B的拆分唯一。道理解释一下如果两个不同的(i, a, b)组合产生了同一个字符串那就意味着同一个字符串有两种不同的配对方式但合法括号序列的配对结果只依赖栈匹配跟配对方法无关配对关系是固定的因此不可能重。这是这道题能用 DP 解的前提也是面试时被追问“你确定结果不重不漏吗”时应该给的回答。4. 两种解法的复杂度账本卡特兰数决定了你的统一上限4.1 结果数量是卡特兰数所有合法括号序列的数量不是多少普通指数它是一个很出名的数列卡特兰数。第 n 项公式是C(n) C(2n, n) / (n 1)前几项n合法括号串数量112235414542814301016796这个数列的递推式C(n) Σ C(i) * C(n-1-i)和gen(k)的拆分公式完全一致所以 DP 解法其实是“生成了所有结构顺带数了数”。对于输出型题目复杂度有一个清晰的下界每个结果长度是2n结果数量是卡特兰数所以至少要输出O(n * C(n))个字符。任何算法都逃不开这个下界。4.2 回溯的时间与空间回溯法访问的节点数并不是2^(2n)因为剪枝会砍掉大量非法分支。但如果要严格证明访问节点数和最终结果数的关系可以认为每个合法前缀都对应一个节点这些节点数量级也在卡特兰数乘多项式级别所以实际总操作量大约也是O(n * C(n))。每次递归到底后path里的字符列表要join成字符串。这个join成本是 O(n)。所以回溯总时间同样是O(n * C(n))。空间方面要区分“算不算结果集”不算结果集时递归栈深度是 2npath 长度是 2n额外空间是 O(n)算结果集时最终答案本身就要占O(n * C(n))字符空间。很多算法分析里说回溯法空间 O(n)指的是额外辅助空间不是最终答案占用的空间。这一点和 DP 比较时尤其重要。4.3 按长度递归的时间与空间按长度递归同样要拼接字符串生成所有结果的时间也是O(n * C(n))。但它的额外空间比回溯要难看一点递归记忆化版本会缓存gen(0)到gen(n-1)的所有结果自底向上 DP 也会持有dp[0]到dp[n-1]的所有列表因此除了最终答案之外额外空间约等于O(n * C(n))。这算是 DP 解法的主要缺点。在力扣原题范围n 8下完全不是问题但如果面试官故意把 n 抬到 15还是用回溯更省内存。两种解法放一块对比对比项回溯按长度递归 DP出发角度生成过程的决策与剪枝最终结果的结构拆分代码复杂度简单清晰简单清晰额外空间O(n)O(n * C(n)) 的子序列缓存可迁移性适合搜索/剪枝变体适合计数和组合计数变体面试讲解难度好讲需要讲清“配对唯一性”4.4 实际提交选择的建议力扣原题1 n 8两种写法提交都不会超时差不了零点几毫秒。我自己的选择标准是平时刷题和面试优先写回溯因为它最容易向别的搜索题迁移如果面试官追问“除了回溯还能怎么写”再写按长度递归顺便带一句结论“这个递推式和卡特兰数的公式一致”如果题目改成“返回合法括号序列的数量”两种写法都别写直接用卡特兰数公式做 O(n) 计算如果题目要求输出第 k 个合法序列可以用 DP 先生成再索引但更好的做法是用计数递推直接确定每一位字符那是另一个话题了。5. 提交与面试里最容易翻车的细节5.1 剪枝条件写成closen会怎样最经典的错误是把第二个分支写成if close_cnt n: path.append()) dfs(open_cnt, close_cnt 1) path.pop()这个条件是“右括号总数没到上限就能加”但它没有考虑当前左括号数量是否镇得住这个右括号。n2 时会生成出())(这种结果路径走到path() , open1, close1此时右括号数小于 n于是再加一个)得到())随后左括号也还没到 n再加一个(得到())(这个串前缀())处右括号已经超过了左括号非法但它照样被记录了下来。所以第二个分支必须保持close open。这个条件等价于“不会对空栈弹栈”是最小且最必要的剪枝。5.2 Java/C语言层面的回溯细节C 版本推荐string path原地改但要注意调完递归后必须pop_back()class Solution { public: vectorstring generateParenthesis(int n) { vectorstring res; string path; functionvoid(int,int) dfs [](int open, int close) { if (open n close n) { res.push_back(path); return; } if (open n) { path.push_back((); dfs(open 1, close); path.pop_back(); } if (close open) { path.push_back()); dfs(open, close 1); path.pop_back(); } }; dfs(0, 0); return res; } };Java 用StringBuilder也是一样的道理append后必须deleteCharAt(sb.length()-1)。如果用不可变String拼接就不需要手动撤销但每次递归都会创建新字符串对象在 n 较大时会有额外的拷贝开销。C 里path.push_back和pop_back配合传引用实测比每次传string拷贝快不少。5.3 调试手段我刷这题时在本地加过计数器统计回溯实际访问的节点数发现 n5 时决策树访问的合法前缀节点大概是几百个远小于2^10 1024还是有点夸实际上 n5 时 2^101024合法前缀节点比这个稍多一点不用写死重点是可以打印。想看出剪枝效果直接在dfs开头加一句print(open%d close%d path%s % (open_cnt, close_cnt, .join(path)))跑一遍 n2可以看到)开头的分支永远不会出现很多半路就越界的分支也不会进入。这种可视化对理解回溯特别有帮助。另一个调试办法是在答案生成后写一个简单的合法性校验把res里每一个串都过一遍is_valid如果发现非法串那就说明剪枝条件写错了。5.4 面试表达的话术如果面试时让你讲这题不建议上来就甩代码。比较好的表达顺序是先说“看到生成所有组合我第一反应是回溯。因为每一步的选择只有左括号和右括号两种本质上是在一棵二叉树上搜索合法叶子。”再讲状态“记录当前路径、左括号数量、右括号数量即可。”然后讲剪枝“左括号只要没用完就能放右括号只能在右括号数小于左括号数的时候放保证任意前缀都合法。”补一个例子“比如 n2 时先一直放左括号到((然后补))得到(())回退后得到()()。”如果对方继续问“还有别的解法吗”再引出(A)B的递推式并说明它对应卡特兰数。这套话术的核心是把“为什么先放左括号”和“为什么右侧有 closeopen 条件”讲清楚。面试官最反感的是背模板式作答所以哪怕多花半分钟画两个节点也比直接念代码有诚意。6. 从括号生成到一类题模型迁移清单6.1 回溯模型迁移从组合题到搜索题括号生成是回溯算法里非常典型的“选择只有两种剪枝条件直接写在状态上”的题目。这套模板稍微改一下就能迁移电话号码的字母组合每一步多选一选择列表来自数字映射的字母串组合总和每步可以选择任意面值剪枝条件是当前和不能超过目标全排列每步从剩余元素中选一个剪枝条件是used数组标记本轮是否已经选过N 皇后每层选一列放皇后冲突检测就是剪枝条件。如果能把括号生成的决策树想明白再去写组合总和和全排列会顺畅很多。因为它们的骨架完全一样只是选择列表和剪枝逻辑换了一下。6.2 递推模型迁移卡特兰数家族的兄弟题按序列长度递归产生的递推式dp[k] sum(dp[i] * dp[k-1-i])在组合数学里几乎无处不在。常见等价问题n 个节点的二叉搜索树形态数n 对括号合法组合数n 个元素通过栈的出栈序列数凸 n2 边形剖分成三角形的方法数。面试如果遇到“某个东西有多少种合法形态”可以先想它是不是卡特兰数。如果是只求数量时不要生成方案直接用组合公式或者 O(n) 的递推公式算省时省力。6.3 括号内容的延伸变体这道题的合法性判定思路还会在整个括号类题型里反复出现最长有效括号找最长子串来自同一套栈匹配思路括号的分数()是 1嵌套翻倍、并列相加可以用栈或递归删除无效的括号从一个字符串里删掉最少的括号使其合法往往用回溯BFS 剪枝括号匹配检查器就是is_valid函数的直接应用。以后看到任何和括号合法性相关的题先想起两个条件数量相等、任意前缀右括号不超过左括号。很多题的本质不过是在这两个条件上加点统计或搜索。个人刷下来最大的感触是这题第一遍最好用回溯第二遍逼自己按长度递归写一遍。我之前一直图省事只背回溯直到在“生成合法圆括号组合的变体”上卡住才回头补齐了 DP 版本。第三次合上题解盲写一遍并尝试对别人讲清楚为什么close open就足够那时候才算真正掌握。最后再分享一个小技巧不管用什么语言递归里尽量别反复拼接新字符串Python 用 list 暂存最后joinC 用string原地pop_back实测 n 到 8 以上时性能差距会明显体现出来。