★ FEATURED ARTICLE 力扣22题“括号生成”是我每隔一段时间就会重新手写一遍的老朋友。刷题进到中段很多人都会被这道题卡一下题目看起来很简单不就是生成 N 对括号的所有合法排列吗可真动手时会发现要么剪枝条件想不清楚要么答案写对了却说不上来“为什么这样写就不会出现非法括号”。这篇文章就把这道题彻底拆开从最暴力的枚举讲到回溯再从回溯讲到动态规划和 BFS顺带记录一些面试现场被追问的真实细节适合准备算法面试的选手、正在复习回溯专题的人以及想把搜索问题理解得更透的开发者。1. 题目本体与复习价值拆解1.1 题目到底在问什么题目输入一个整数 n表示括号的对数要求输出所有由 n 个左括号和 n 个右括号组成的合法字符串。所谓“合法”就是任意前缀中左括号的数量始终不少于右括号的数量整个字符串扫描结束后左右括号数量相等。举个例子n 2 时输出是[(()), ()()]。这里要注意)(这类字符串虽然在字符数量上刚好是两左两右但从前缀)开始就已经非法所以不可能进入结果集。))((同理前缀中右括号数量已经超过了左括号数量。还有一个容易忽略的边界n 0 时输出来说应该是一个空字符串集合在实现层面通常返回[]。这个边界看似无聊但在后面用动态规划推导时恰恰是这一条让递推公式能够成立所以放到后面一起理解会更清楚。这道题的本质是一道“生成合法序列”的组合问题。答案数量并不是 2^n 这种简单增长而是第 n 个卡特兰数。n 1 时 1 个n 2 时 2 个n 3 时 5 个n 4 时 14 个。这个增长趋势在面试分析复杂度时是很大的亮点能主动说出“合法解数量等于卡特兰数”和只说“指数级增长”是完全不同的两个水平。1.2 为什么这道题值得反复复习我在不同阶段刷这道题感受完全不同。第一次接触觉得就是要“凑”出所有组合后来发现它是对“回溯搜索”非常标准的一次训练每个递归分支都有明确的扩展条件和剪枝条件变量少、逻辑直观非常适合作为回溯专题的入门题和检验题。它综合了四个能力点穷举思想每个位置只有两种选择左括号或右括号。剪枝意识不是所有分支都需要走完两条约束能把大量非法分支提前挡住。递归状态管理字符串是传值拼接还是用可变对象后撤销写法和性能差别很大。复杂度推导答案数量是卡特兰数这个推导过程本身就是面试考点。还有一点这道题是很多括号类问题的母题。“有效的括号”是它的反向判定版本“最长有效括号”是它的区间优化版本还有“移除无效括号”这类变体本质上都在用括号合法性约束做文章。把 22 题吃透等于把一整类问题的思考框架都拿下了这也是我每次复习回溯总要先写一遍它的原因。2. 思路推导从暴力枚举到回溯剪枝2.1 第一时间想到的暴力做法很多第一次接触这道题的人第一反应是直接把所有长度为 2n、由左右括号组成的字符串都生成出来然后逐个判断是否合法。这个思路本身没有问题问题出在量级上。n 对括号每个位置 2 种选择总序列数量是 2^(2n) 个。n 5 时是 1024 个还能忍n 8 时是 65536 个n 10 时直接到 1048576再往上就是指数爆炸。而其中合法序列只有卡特兰数那么多个n 10 时合法结果是 16796 个非法序列占了绝大多数。生成所有再筛选意味着大量计算时间都花在注定被淘汰的字符串上。判断函数本身并不难写维护一个计数器遇到左括号加一遇到右括号减一扫描过程中一旦计数器为负就立刻返回非法扫描完最后计数器必须归零。这个判断是 O(n)整体复杂度就是 O(2^(2n) * n)完全不可接受。但暴力解法有一个价值它让我们确认了“合法解数量远小于所有可能排列”这个事实。因此正确的方向不是优化判断速度而是从源头就避免生成非法序列这就是剪枝和回溯的出发点。2.2 合法括号序列的核心约束要在一开始就避免非法序列得先抽象出合法的本质约束其实只有两条左括号数量不能超过 n。右括号数量不能超过左括号数量。这两句话是整道题的灵魂。翻译成代码条件当left n时可以尝试加一个左括号当right left时才可以加一个右括号。两个条件都满足时两个分支都能走只满足其中一个就只走对应的分支都不满足就说明当前字符串长度已经到 2n需要处理结果。为什么要用而不是这是新手最容易写错的地方。left n会让左括号多放一次直接生成“第 n1 个左括号”的非法串。right left则会允许右括号数量与左括号数量相等时继续加右括号从这一刻起当前前缀已经不合法后面无论怎么补都不可能翻转回来。所以这两个地方必须是严格的。这个约束的本质可以理解成“配对问题里的前缀性质”任何时候已经出现的右括号必须有足够的左括号去配它。生活化一点想就像排队进场必须有一个人拿着左括号票先进去右括号票持有者才能跟着进右括号永远不能比左括号更早进场。这个类比我在面试中也经常用用来快速向面试官证明思路正确。2.3 回溯搜索框架如何落地回溯本质是带撤销的深度优先搜索。对这道题来说每个递归状态只需要记录三样东西当前已构造的字符串、已用的左括号数量、已用的右括号数量。递归框架是典型的“三件套”判定终止条件如果当前字符串长度为 2n说明左右括号各用完了 n 个直接加入结果。枚举合法分支先判断能否放左括号能放就走再判断能否放右括号能放就走。状态恢复如果用的是可变对象构造字符串递归返回后要撤销本分支的修改。这里有一个很多文章没细讲的选择题字符串对象到底怎么管理我见过两种主流写法。第一种是传值写法每次递归都传入新的字符串例如dfs(left 1, right, cur ()。因为字符串是不可变对象拼接操作生成的就是一个全新的字符串递归返回后不需要做任何清理。这种写法逻辑最不容易出错缺点是中间会生成大量临时字符串有拷贝开销。第二种是引用写法用StringBuilder或可变字符数组先append(()进入递归返回后立刻deleteCharAt(...)删除末尾。性能更好但必须记住“加什么就删什么”一旦某个分支忘了恢复状态就会被污染产生非常隐蔽的 bug。我的建议是面试中追求稳先用传值写法把思路演示清楚如果面试官追问性能优化再展示可变对象的写法。两种都能写本身就是加分项。3. 回溯算法的标准实现与状态树模拟3.1 参数设计与终止条件详解函数签名如下dfs(left, right, cur)其中 left 和 right 是已经使用的左右括号数量cur 是当前构造中的字符串n 和 result 从外层闭包或参数传入。某些写法里会把这个函数命名为backtrack本质上一样。终止条件我习惯写成len(cur) 2 * n。这时候必然有left n且right n因为每次递归只会增加一个字符而两个分支条件一直保证左右数量都不会超过 n。也有人写成if left n and right n效果完全一致只是多判断一次。两种都见过建议按团队代码风格来不必纠结。还有一个小细节值得留意递归函数返回后是否需要 actions如果用的是传值写法什么都不用做如果用 StringBuilder必须在每次递归返回后删除刚追加的字符。删除的地方要和 append 的地方严格配对我在 3.2 的 Java 代码里会标注得很明确。3.2 Python 与 Java 实现及逐行解读Python 版本优先推荐代码最简洁from typing import List class Solution: def generateParenthesis(self, n: int) - List[str]: res [] def dfs(left: int, right: int, cur: str) - None: if len(cur) 2 * n: res.append(cur) return if left n: dfs(left 1, right, cur () if right left: dfs(left, right 1, cur )) dfs(0, 0, ) return res这段代码的精髓在最后两个 if 的顺序先尝试左括号再尝试右括号。这个顺序决定了输出结果是字典序排列因为 ( 的 ASCII 值比 ) 小DFS 先走左分支会让更“靠左”的字符串先出现。比如 n 3 输出就是[((())), (()()), (())(), ()(()), ()()()]正好是字典序。Java 版本处理字符串时可以用 String 传值也可以用 StringBuilder 引用型。引用型写出来是这样的import java.util.ArrayList; import java.util.List; class Solution { public ListString generateParenthesis(int n) { ListString res new ArrayList(); backtrack(new StringBuilder(), 0, 0, n, res); return res; } private void backtrack(StringBuilder sb, int left, int right, int n, ListString res) { if (sb.length() 2 * n) { res.add(sb.toString()); return; } if (left n) { sb.append((); backtrack(sb, left 1, right, n, res); sb.deleteCharAt(sb.length() - 1); } if (right left) { sb.append()); backtrack(sb, left, right 1, n, res); sb.deleteCharAt(sb.length() - 1); } } }注意deleteCharAt(sb.length() - 1)这一行的位置。它必须紧跟在递归调用之后无论递归内部发生了什么只要返回到当前层就得把刚才追加的字符删掉。我也见过有人把两个 append 放在最前面、最后统一删除那样问题更大因为如果第一个 if 走了、第二个 if 没走删除逻辑就错位了。写引用型回溯时删改动作一定要和添加动作完全对称。3.3 用 n 2 手动推演整个递归过程理论讲了半天不如手动走一遍 n 2 的状态树这是复习时最值得做的事。从dfs(0, 0, )开始left0, right0两个条件都满足但先走左括号分支进入dfs(1, 0, ()。在dfs(1, 0, ()中left 2成立走分支进入dfs(2, 0, (()。在dfs(2, 0, (()中left 2不成立但right left即0 2成立进入dfs(2, 1, (())然后继续走right left进入dfs(2, 2, (()))。此时长度等于 4记录(())返回。回到dfs(1, 0, ()这一层刚才的左分支已经走完再看右分支right left即0 1成立进入dfs(1, 1, ())。在dfs(1, 1, ())中left 2成立走dfs(2, 1, ()()随后走right left得到dfs(2, 2, ()())记录()()。所有分支结束结果集为[(()), ()()]。这里最容易看晕的地方是第 4 步为什么dfs(1, 0, ()还能走右括号分支因为在它这一层left 还是传入时的 1而不是左分支里的 2。递归每一层都有自己的局部参数这就是“状态隔离”的含义。一旦用了类字段或全局变量来存 left 和 right这个隔离就会被破坏这也是很多开发者写复杂回溯时出错的根源。3.4 复杂度分析为什么是卡特兰数合法括号序列的数量恰好是第 n 个卡特兰数公式是C(2n, n) / (n 1)以 n 3 验证C(6, 3) 2020 除以 4 等于 5和已知结论一致。这个公式不是背出来的其核心推导思想是在所有 2^(2n) 个等概率序列中合法序列占比是 1/(n1)。这个结论可以借助“反射原理”证明但对面试而言至少要知道结果并能手算验证。时间复杂度方面回溯访问的每个合法叶子节点都会被加入结果集合而卡特兰数的渐进增长率是4^n / (n^(3/2) * sqrt(pi))所以通常说时间复杂度是 O(4^n / sqrt(n))。再具体一点这棵树里每个节点都要做常数额外判断时间复杂度本质上和“生成结果所需的总字符量”同阶。空间复杂度则是 O(n)递归深度最多 2n每个栈帧保存当前路径字符串长度最多 2n因此线性增长。有些地方会把结果数组的空间也算进去那就需要单独加上输出规模。4. 除了回溯动态规划与 BFS 两条替代路线4.1 动态规划的状态转移与含义这道题除了回溯还有一条经典的动态规划思路而且它推导出来的递归公式对理解卡特兰数非常有用。定义dp[i]为“i 对括号能够生成的所有合法字符串列表”。这里最关键的是dp[0] []可以理解成空字符串代表 0 对括号的唯一组合它是后面所有组合的基础。为什么必须放一个空字符串因为后续拼接时左右两边都可能从空串开始没有这个元素迭代根本没法启动。状态转移的核心是这样一个观察任意一个合法括号序列最外层总是有一对左右括号它可以看成“外层的()包裹了一部分序列后面再接另一部分序列”。也就是说一个合法序列可以写成( A ) B其中 A 和 B 都是各自合法的括号序列。假设 A 由 p 对括号组成B 由 q 对括号组成那么 p q i - 1因为外层那一对已经用掉了 1 对。于是转移方程就出来了dp[i] 对每个 p 从 0 到 i-1 从 dp[p] 取一个 A从 dp[i-1-p] 取一个 B 组合成 ( A ) B这个分解思路值得多说几句。它等价于从递归视角出发把规模为 i 的问题拆成两个子问题外层一对括号固定内部规模为 p右侧规模为 i-1-p。只要 A 和 B 都是合法序列那么拼接结果一定是合法序列反过来任何一个合法序列也一定能拆成这个样子。所以这是一个完备的划分不会漏解也不会重复。4.2 DP 代码实现与对比分析动态规划的 Python 代码非常直观from typing import List class Solution: def generateParenthesis(self, n: int) - List[str]: if n 0: return [] dp [[] for _ in range(n 1)] dp[0] [] for i in range(1, n 1): cur [] for p in range(i): q i - 1 - p for left in dp[p]: for right in dp[q]: cur.append(( left ) right) dp[i] cur return dp[n]拿 i 2 来验证p 0 时 q 1left 取dp[0]里的空串right 取dp[1]里的()组合得到() ()即()()p 1 时 q 0left 取dp[1]里的()right 取空串组合得到( () )即(())。所以dp[2]结果是[()(), (())]。注意顺序回溯法结果是[(()), ()()]DP 结果是[()(), (())]两种顺序不一样但都能通过判题。如果题目有“按字典序输出”的隐藏要求DP 写法就需要额外排序这是面试时容易被追问的点。复杂度上DP 的时间复杂度同样是 O(4^n / sqrt(n))因为生成结果的规模就是卡特兰数规模但空间复杂度比回溯要大需要同时保存从 dp[0] 到 dp[i-1] 的所有中间结果。可以理解为用内存换来了代码结构的规律性。4.3 BFS 层序遍历思路这道题也可以基于队列做宽度优先搜索。状态三元组是 (left, right, cur)从 (0, 0, ) 出发每层扩展时将满足条件的两个后继入队。from collections import deque from typing import List def generateParenthesis_bfs(n: int) - List[str]: res [] q deque([(0, 0, )]) while q: left, right, cur q.popleft() if len(cur) 2 * n: res.append(cur) continue if left n: q.append((left 1, right, cur ()) if right left: q.append((left, right 1, cur ))) return resBFS 的好处是搜索过程按长度分层推进很多人能更直观地看到“长度为 1 时的合法前缀只有(”“长度为 2 时只有(()和()”这一层层的发展。但代价是内存占用比 DFS 高因为队首和队尾之间会同时保留一层的多个路径中间串而递归写法同一时刻只有一条路径在栈上。我在面试模拟中很少看到候选人主动提 BFS但如果提到面试官往往会露出比较惊喜的表情因为这证明你不只会套递归模板而是真的理解搜索的空间换时间关系。这道题用 BFS 能过但效率不是最优更多时候它是用来证明理解深度的“加分解法”。5. 常见错误与面试实战记录5.1 我见过的三类典型写错方式第一类括号数量约束写反。最常见的是把右括号条件写成right n或者left right。前者会让右括号总想补满 n 个于是在left1, right1这个状态下继续放右括号得到())这种前缀就非法的字符串。后者更离谱等于是要求左括号始终多于右括号最终会漏掉大量合法序列。检查方法很简单把 n 设为 2手动走一下状态树看看有没有出现非法叶子。第二类状态管理失效。使用 StringBuilder 或 ArrayList 时递归返回后忘记删除刚追加的字符。例如 Java 代码里只有sb.append(()跟着递归没有配对的deleteCharAt那么第二层递归返回后字符串尾部永远多一个 (整个分支全部错乱。这种 bug 很隐蔽因为部分用例可能恰好能跑过只有在 n 稍微增大时才暴露。排查时在函数入口打印当前 sb 内容一眼就能看出状态没有回滚。第三类输出去重或顺序错误。有些回写会额外使用 Set 来去重这本身不算错但如果同一个解通过不同路径重复到达就说明状态设计有冗余。在 22 题里两个约束条件保证每个合法序列只有唯一的生成路径根本不需要去重。如果发现结果里有重复项优先检查是不是右括号条件用了导致同一条路径在某个节点能走两次。还有一种和语言相关的坑Python 里写cur (然后再传递如果把cur当成了可变的局部修改可能会在循环或递归中造成状态污染。我推荐直接用cur (作为函数参数减少中间变量这是我在实践中觉得最稳妥的写法。5.2 和面试官在这个题上的高频追问追问一n 0 时你的代码返回什么我的 Python 回溯代码会返回[]。如果题目希望返回空列表需要加一个特殊判断。面试官问这个问题主要是确认你注意了边界条件回答时最好主动说明“根据题目对空串的定义决定”。追问二能不能不生成所有结果只输出数量能直接用卡特兰数公式C(2n, n)/(n1)或者用递推。只要求计数时这个答案简洁且复杂度 O(n) 可以接受如果还要求对超大 n 取模就得用组合数学和快速幂。追问三要求按字典序输出你的回溯需要改吗不需要。因为回溯总是先尝试放左括号天然按字典序输出。但如果候选人现场先写了动态规划就必须意识到 dp 的拼接顺序不一定严格字典序需要补一句“要字典序的话回溯更合适”。追问四能否用非递归方式解这里就可以引出 BFS 或显式栈实现 DFS。候选人能在递归模板之外再写出非递归版本面试官通常会愿意继续深入聊状态管理、队列选型等话题。追问五把括号字符换成别的字符对比如A和B解法变吗完全不变只要定义 A 为“开”B 为“闭”所有约束和代码结构照搬。这个抽象能力很重要面试官想看你是否能从具体题面中剥离出本质。5.3 衍生题目清单与迁移思路这道题的很多变体都围绕同一个核心约束展开我整理了一张简表衍生题核心思路有效的括号给定字符串判断是否合法线性扫描计数器或栈最长有效括号求最长合法连续子串动态规划或栈移除无效的括号删除最少字符使字符串合法先扫描确定多余位置再通过DFS修正第 k 个合法序列回溯加组合计数剪枝提前计算卡特兰数缩小分支范围左右括号带权或染色在回溯基础上给左右括号附加生成条件结构几乎不变举“最长有效括号”为例它看似完全不同的题但核心状态“右括号数量不能超过左括号”依然存在只是变成了扫描过程中维护一个前缀计数遇到违约时从某个位置重新开始计算。理解了 22 题的约束再去看最长有效括号的栈解法会觉得顺畅很多。6. 复习方法论怎样才算真正吃透6.1 画状态树与限时复现我复习这道题最常用的是“三遍法”。第一遍手动画状态树。取 n 2 或 n 3在纸上把dfs(left, right, cur)的每个节点都展开标注每个节点的 left、right、cur以及哪些分支因为什么条件被剪掉。这个过程能极大帮助理解递归边界。第二遍限时复现代码。不看任何参考资料设定 15 分钟在编辑器里从零写出回溯解法并跑通样例。复现时我会刻意把剪枝条件读出声left 小于 n 才能放左括号right 小于 left 才能放右括号。朗读能帮助大脑把逻辑固定下来。第三遍对比解法写 DP。要求自己不看答案写出动态规划版本然后对比两个版本的结果集合是否一致顺序差异在哪里。能完成这一步基本上对这道题的理解就不只是停留在“背模板”层面了。6.2 语言细节带来的坑不同的语言写这道题踩坑位置完全不同。Python 里最容易出现的问题是把不可变字符串和可变列表混着用比如在列表中 append 字符串后又想修改某一位忘了字符串是不可变对象于是改用列表后又忘了在递归返回时pop()。Java 和 C 的坑主要在 StringBuilder 和引用的生命周期上。Java 里sb.append()后不deleteCharAt()状态就会一路增长C 如果传引用string cur且用push_back和pop_back管理也需要严格配对。面试时我的习惯是先和面试官确认语言然后采用该语言里最不容易出错的状态管理方式。Python 用传值字符串Java 用String 的不可变拼接这样能最大程度避免在高压环境下出现状态污染。只有在面试官明确问到性能时再切换成可变对象写法并解释取舍。6.3 我的个人收尾经验复习这道题到后期我给自己增加了两个“自残式”练习一是故意改错一个剪枝条件比如把right left改成right left然后预测输出会多出哪些字符串二是只用文字描述算法流程让一个没做过这道题的人照着描述写出代码。这两个练习能快速暴露我对约束条件的理解是否足够扎实。另一个体会是22 题的价值不只在回溯本身。它把“生成合法集合”的两种经典思路放在同一道题里一种是 DFS 加剪枝的自顶向下一种是组合子问题的自底向上。以后遇到任何需要“生成所有合法结构”的题比如生成所有合法子集、所有满足条件的路径、所有语法树变体我都会先问自己能不能像回溯这样一条路走到黑再剪能不能像卡特兰数那样把问题拆成左右两个子集合这种思维迁移比记住某一题的代码重要得多。
阅读完成 · 觉得有帮助？
