力扣第 22 题括号生成我刷了很多遍每次准备面试前还是会把它重新过一遍。这道题几乎把回溯算法的核心要素全部集齐了递归树长什么样、哪些分支可以剪掉、状态怎么记录、什么时候需要撤销选择。题目看着就一句话但展开之后深度相当可观从暴力枚举到剪枝再到动态规划甚至能一直聊到卡塔兰数。这篇复习笔记写给三类人一是刚开始接触回溯、想找一个经典入门题的读者二是面试前想快速把 DFS 状态设计捡起来的开发者三是已经刷过这题但总感觉“思路懂代码写不顺”的人。我会把计算过程、剪枝推导、代码落地、常见翻车点全部拆开讲尽量让看完的人不用再翻别的资料。1. 先回头看题目括号生成的题干和真正的考点1.1 题干与示例题目要求非常简洁给定一个数字 nn 代表生成括号的对数请你生成所有可能的、并且有效的括号组合。有效意思是左括号和右括号必须正确配对任意前缀里右括号数量不能超过左括号数量最后左右括号总数相等。举个例子n3 时答案一共有 5 个((())) (()()) (())() ()(()) ()()()如果自己手动枚举会发现 n1 时答案只有 1 个()n2 时是 2 个(())和()()n4 时答案就蹦到 14 个了。这个数字序列 1, 2, 5, 14 正是卡塔兰数Catalan Number的开头后面会详细算。很多人以为这道题刷过一遍就结束了其实它特别适合作为回溯算法的“基准测试题”。因为它的搜索空间是清晰可控的每一步选择只有两个选项约束条件也很直观非常适合用来验证你对递归状态、剪枝条件、边界处理的理解是不是真的到位。1.2 这道题到底在考什么表面上考的是“生成组合”本质上考的是三件事递归穷举、合法条件剪枝、状态回溯。递归穷举很容易理解长度为 2n 的字符串每个位置要么填(要么填)如果把所有情况都列出来那就是 2 的 2n 次方种。这个数量爆炸得非常快n8 的时候2 的 16 次方是 65536看着还不算离谱n10 时是 1048576已经超过一百万n12 时是 1670 万。真实面试里 n 一般给到 8 以内暴力搜可能勉强能过但这不是出题人想要的解法。合法条件剪枝是这题的灵魂。它能让你在递归过程中只沿着可能组成有效序列的分支走而不是先生成完整字符串再回头一个个校验。这个约束我会在下一节详细推导这里先记住一个核心结论只要保证每一步生成出来的前缀串都是合法的最终拼接出来的整个字符串一定合法。状态回溯则取决于你用什么语言。Python 里如果用 list 保存路径递归返回时必须把刚才添加的字符移除如果用字符串拼接因为字符串是不可变的每层递归天然生成新对象就不需要手动撤销。这个细节看起来小却是一堆人调试半天找不到 bug 的原因。1.3 三种思路的取舍对比对于括号生成常见解法有三条路线暴力枚举、回溯剪枝、动态规划。三条路线不是孤立的而是层层递进的关系。解法核心思想时间复杂度空间复杂度适用场景暴力枚举生成所有 2^(2n) 个括号串再逐个校验合法性O(2^(2n) * n)O(n)理解题目、推导优化时用回溯剪枝只递归合法的前缀build 过程中剪掉非法分支O(4^n / sqrt(n))O(n)标准最优解面试主推动态规划用 dp[i] 表示 i 对括号的全部组合通过拼接构造O(C_n * n^2) 左右O(C_n * n)面试追问思路时展示递推能力回溯的时间复杂度看起来还是指数级但它的“指数”是卡塔兰数的量级比暴力枚举小很多。n8 时暴力要枚举 65536 个串每个还要做一次长度 16 的校验回溯实际走的合法状态节点要少得多。这道题里回溯就是标准答案你需要把这个结论打磨到能自然讲出来的程度。2. 剪枝条件从哪来括号合法性的两个本质约束2.1 前缀性质任何时候右括号都不能超过左括号聊括号生成必须先聊“什么样的括号组合是合法的”。很多人只知道左右数量相等比如())(左右数量都是 2但明显不合法。问题就出在它中间某一段前缀里右括号数量压过了左括号数量。把左括号看成“开灯”右括号看成“关灯”合法序列就是整个过程里灯永远是亮着或刚好灭掉等量绝不能在灯已经关着的时候再执行一次关灯。换句话说从左往右扫描任意一个合法括号串任意位置前面的左括号数一定大于或等于右括号数。这个性质叫括号串的前缀合法性。反过来说如果我们在拼接一个串的过程中始终保证每添加一个字符后右括号数量都没有超过左括号数量那么最终得到的串一定合法。这给了我们一个非常强的剪枝规则每次选择添加右括号)之前必须检查当前已放的右括号数量是否小于左括号数量。只有右括号数严格小于左括号数时放右括号才安全。2.2 剩余数量约束左右都不能超过 n第二个约束则更简单一共只有 n 对括号所以左括号最多放 n 个右括号也最多放 n 个。递归的时候记录两个变量 left 和 right分别表示已经放了多少个左括号和右括号。添加左括号的条件就是 left n只要左括号还没放完就可以继续放。注意这里不是 left n因为 left 是从 0 开始计数的n 对括号最多允许 left 取到 n。如果允许 left 走到 n1就相当于多放了一个左括号整个串的总长度也会失控。添加右括号的条件是 right left 且 right n。实际上当 right left 时right 一定还没有达到 n因为 left 最大只有 n所以 right 最多也就 n-1因此只写 right left 就足够了。这个条件同时保证了“数量不超”和“前缀合法”两层含义非常精妙。2.3 把这个性质画成搜索树光讲理论不好记我建议你亲手画一棵 n2 的递归树。从空串开始第一层只能放(因为 right left 里 right 是 0left 是 00 0 不成立放右括号非法。第二层有两个分支放(得到((放)得到()。继续往下走((只能放)变成(()()可以放(变成()(。最后所有路径都会在长度等于 4、left2 且 right2 时结束得到(())和()()。画完这棵树你会发现所有非法分支根本就不会被展开。比如第二层那个放右括号到)的情况从第一行就被切掉了整棵树的规模被明显压缩。这正是回溯优于暴力的地方你不是在结果里筛掉非法答案而是在搜索过程中就不给非法路径任何机会。理解了这棵树你就把括号生成这道题的“递归心智模型”建立起来了。后面写代码其实只是把这棵树用递归函数表达出来而已。3. 从暴力到回溯一行一行写出能过的代码3.1 暴力枚举先把最笨的思路跑通我建议刷这题的时候先写一遍暴力不要一上来就回溯。暴力版本虽然慢但它能把题目边界、合法校验逻辑都暴露出来后面写回溯时你对“为什么剪枝”会有更体感的认识。暴力思路分两步先递归生成所有长度为 2n 的括号串然后写一个校验函数判断它是否合法。代码如下def generateParenthesis_brute(n: int): def valid(s): bal 0 for c in s: bal 1 if c ( else -1 if bal 0: return False return bal 0 res [] def dfs(path): if len(path) 2 * n: if valid(path): res.append(.join(path)) return path.append(() dfs(path) path.pop() path.append()) dfs(path) path.pop() dfs([]) return res校验逻辑里bal 就是前缀差等于 0 说明左右数量刚好平衡小于 0 说明出现了右括号多于左括号的非法前缀。走完整个串后 bal 必须回到 0表示左右括号总数相等。这个暴力版本的时间复杂度是 O(2^(2n) * n)列表里有 2^(2n) 个串每个串要花 O(n) 的时间校验。n 很小的时候感觉不到问题n10 基本就跑不动了。它的意义在于帮你想清楚“合法”到底是怎么定义的也让你直观感受到大量无效组合被白白生成。3.2 剪枝回溯标准写法的三个重点真正的标准解法是在递归过程中同步维护 left 和 right 两个状态只走合法的方向。用 Python 写最简单的是字符串版本def generateParenthesis(n: int): res [] def dfs(left, right, s): if len(s) 2 * n: res.append(s) return if left n: dfs(left 1, right, s () if right left: dfs(left, right 1, s )) dfs(0, 0, ) return res这个版本有三个重点面试时也是围绕这三个点追问的。第一个重点函数的输入状态是left, right, ss 是当前已经拼好的前缀。这里 s 用不可变字符串每递归一次生成新字符串所以不需要“撤销”函数返回时上层 s 自动恢复。第二个重点递归分支顺序写成先加左括号、再加右括号。这样会保证结果里面像((()))这种“左括号密集”的序列排在前面()()()这种“平铺”的序列排在后面。如果你用 list 改写成经典回溯版结果顺序也一致。第三个重点终止条件是len(s) 2 * n。因为每一步都保证了前缀合法走完 2n 步时 left 和 right 必然都等于 n所以不需要再额外判断 left n and right n。如果你更想用标准回溯模板把路径当成 list 来维护就要注意显式撤销def generateParenthesis(n: int): res [] def dfs(left, right, path): if len(path) 2 * n: res.append(.join(path)) return if left n: path.append(() dfs(left 1, right, path) path.pop() if right left: path.append()) dfs(left, right 1, path) path.pop() dfs(0, 0, []) return reslist 版本和字符串版本本质一样但 list 是可变对象往递归里传的是同一个引用所以从深层递归回来后如果不 poppath 就会带着错误的状态进入下一个兄弟分支。这是回溯模板的通用规则改变了共享状态就要撤销字符串因为不可变所以天然免去这一步。我在实际刷题时更习惯字符串版本因为在 Python 里它更简洁不容易手滑漏掉 pop。3.3 复杂度到底是多少卡塔兰数的直观理解括号生成的结果数量是卡塔兰数 C_n 1/(n1) * C(2n, n)。n3 时是 5n4 时是 14n5 时是 42。这个数字增长很快但仍然比 2^(2n) 小很多。回溯算法实际遍历的节点数和最终结果数量同阶大致是 O(C_n * n)其中 n 是每个结果串的长度因子因为生成每个长度为 2n 的串需要走 2n 层递归。空间上递归深度最多 2n所以额外空间是 O(n)结果列表本身不算在内。面试时你不需要背卡塔兰数的严格证明只需要能说清楚合法括号序列的数量比所有括号序列少得多回溯通过剪枝只探索合法前缀所以比暴力枚举高效。如果面试官继续追问卡塔兰数怎么算把公式写出来即可。4. 刷题现场最容易翻车的三个地方4.1 剪枝条件写成 right left看到不少人在写第二个分支时会把条件写成if right left觉得“右括号数量不能比左括号多那相等时也应该能放右括号吧”。这个思路看着合理实际会把搜索树拖大。当 right left 时比如当前串是()left 和 right 都为 1这时候再放一个右括号得到())这个前缀的右括号数量已经大于左括号数量后面无论如何补救都不可能变成合法串。所以 right 等于 left 时放右括号是必然非法的分支。正确条件是right left等于号不放行。从效率上看写成 right left 不会导致最终结果错误因为非法分支会走到底但无法满足长度条件吗其实也有可能会产生长度正好达到 2n 的非法路径因为 left 可能已经达到 nright 已经小于 n 时right left 或 right left让我再模拟一下如果 right left而 left 还没有到 n那么 right left 成立可以放右括号变成 right left此后这个节点再也没有可扩展的合法方向路径长度会卡在某个值小于 2n不会进入结果因为左括号条件 left n 可能还满足不此时 right left但 left n 仍然满足所以还能继续加左括号最终可能继续扩展形成像())(这样长度为 4、left2、right2 的非法串最终通过 len(path) 2n 进入结果集但校验没做所以会返回非法结果等等让我仔细想路径left1, right0 时放 ) - left1, right1合法串()。 在 left1, right1 时若条件 right left 成立会放 ) - left1, right2串())前缀已经非法。 从 left1, right2 出发leftnn2成立可以放 ( - left2, right2串())(长度达到4left2 right2进入结果集。这个串())(合法吗不合法因为第三个位置 ) 使得前缀右括号数超过了左括号数。而这个串左右总数相等通过了 len 条件最终会被错误地添加到结果里。因此写成 right left 会产生非法结果这就更严重了。除非递归终态同时校验 left n and right n 也是不够的因为左右相等所以还需要校验前缀合法。我的回溯代码里没有额外的 valid 校验依赖的就是剪枝条件。所以 right left 会把非法串放进来。四份之一处在 left1,right0 放右括号是允许的按 rightleft10不成立所以第一步不能放右括号。所以())(生成路径需要从合法前缀开始中间经过 rightleft 放右括号。它最终被加入。所以结论是写成 right left 会产生非法结果不只是效率低。这个非常重要且严重。我前面的草稿中说“不会产生非法结果”是错的需要修正。让我确认标准条件 rightleft 是否能阻止())(生成第一步不能放右括号。所以不会。如果 left1,right0 时条件 right left 是 01 成立可以直接放右括号得到)然后 left1,right1然后为什么继续...)到)(? 从)状态再放)left1,right1 时 rightleft 成立放右括号变))left1,right2leftn 继续放左())? 左加括号变())(总之能生成非法串。所以这个坑非常严重。我写博文时要讲清楚写成 right left 会直接把非法串放进结果集因为前缀不再合法而你后续没有再做校验。这一点是很多人代码跑出多余结果的罪魁祸首。同理第一个分支如果写成 left n 也会导致超量。因为 left 会变成 n1长度最终超过 2n终止条件 len(path)2n 可能永远达不到实际上 left 可以一直加直到超过 n比如 n2left 可以到3然后 right 补齐到2长度到达5大于4无法等于2n所以不会进入结果但会浪费搜索。不过为了代码正确性和直觉左括号条件应该用 left n。4.2 状态恢复该不该做关于状态恢复我在前面代码里已经展示了两种写法。实际调试时最常见的现象是输出结果出现大量重复组合或者组合里的字符顺序错乱。如果你用 list 作为 path却忘记在递归返回后 pop那么深层递归修改后的 path 会污染到兄弟分支。比如当前层先进入了放左括号的分支回来后 path 末尾仍然是刚刚加进去的(这时候再进入放右括号的分支就会带着一个多余的左括号继续拼最终结果完全错乱。解决办法很机械append 和 pop 必须在同一个递归调用的前后对称出现。我建议用字符串版本写这道题因为 Python 字符串s (会生成新对象递归返回后 s 自动变回进入递归前的值这个心智负担直接消失。在其他语言里要注意C 用 string 引用或者 Java 用 StringBuilder也必须在递归回退后删除尾部字符。如果你在面试中被要求手写 C 或 Java务必把pop_back()或deleteCharAt()当成和递归调用同等重要的步骤。4.3 边界情况n0 和 n1这道题给 n 的范围通常是 0 到 8所以 n0 是必须处理的边界。n0 时没有任何括号对合理答案应该是一个空串[]还是空列表[]不同版本题面有差异部分老版中文题面期望[]而最新版本通常接受[]。我建议提交前看一眼题目的示例和预期输出如果是自己写单元测试也把这个边界单独列出来。从思路一致性讲n0 时结果应该只有一个空串因为空串是合法的括号组合。动态规划解法里 dp[0] [] 也必须这样定义否则后面组合时会缺一层基础。n1 是另一个好调试的边界答案只有()。如果你的代码在 n1 时输出了空列表多半是终止条件写成了len(s) 2*n - 1或者 left 和 right 的初始值写错。拿 n1 手动走一遍递归很快就能发现问题。5. 面试延伸从回溯到动态规划再到同类变体5.1 动态规划解法的递推逻辑回溯是这题的常规解但面试官经常追问“能不能用动态规划做”。能而且思路非常优雅。定义 dp[i] 为 i 对括号能生成的全部合法字符组合。dp[0] []。递推的关键在于枚举最后一对闭合括号的位置一个合法的括号序列可以看成是( A ) B其中 A 和 B 都是合法括号序列A 由 j 对括号组成B 由 i - 1 - j 对括号组成。为什么一定存在这样的拆分因为最左边的左括号必然匹配某个右括号A 就是它们中间包含的内容B 就是这对括号右侧剩余的内容。j 从 0 遍历到 i-1覆盖所有划分情况。def generateParenthesis_dp(n: int): dp [[] for _ in range(n 1)] dp[0] [] for i in range(1, n 1): cur [] for j in range(i): for left_part in dp[j]: for right_part in dp[i - 1 - j]: cur.append(( left_part ) right_part) dp[i] cur return dp[n]这段代码跑出来的结果顺序和回溯版本不完全一样比如 n3 时 DP 可能先输出()()()。如果题目对顺序有要求需要排序或者改用回溯。这正好说明两种思路的差异回溯是按字符串位置逐步填空DP 是按规模划分子问题它们写出代码的节奏完全不同。5.2 相关变体题的关键区别理解了括号生成再去看其他括号类题目会轻松很多。最常见的几道变体有判断给定括号串是否合法。这类题的核心就是“前缀右括号数不超过左括号数”一个计数器就能解决。最长有效括号长度。这题要从任意位置开始找比“判断整体是否合法”复杂得多需要动规或者栈配合。删除最少的括号使剩余串合法。这道题要把回溯、广度优先搜索和非法位置判断结合起来难度高一个档次。带通配符的括号匹配。通配符可以当左括号、右括号或者空字符判断复杂度增加。如果你在面试中完整写出了 22 题的复盘可以把这些变体作为延伸话题提一两句面试官会认为你对这块知识是有体系地理解的而不是只背了一道题的答案。5.3 面试现场怎么把思考过程讲清楚我建议的讲解顺序是先给暴力思路再指出无效组合太多然后引出约束条件最后写回溯代码。不要上来就写最优解因为面试官想看的往往不是代码本身而是你的思维路径。具体话术可以这样组织先说明要枚举 2^(2n) 种情况显然可以优化接着指出任意时刻右括号不能超过左括号所以递归时维护两个计数最后说明左括号有条件地加、右括号有条件地加走到 2n 长度时加入答案。讲到这里代码基本已经在面试官心里写完了你再落笔会顺畅很多。如果面试官追问复杂度可以说“结果数量是卡塔兰数回溯遍历的节点和结果数量同阶”。能说出卡塔兰数已经是一个不错的加分项。6. 写在最后这道题怎么复习才不容易忘我个人复习括号生成的心得是不要背代码而要背“三个决策点”。第一这一步能不能放左括号条件是左括号还没用完第二这一步能不能放右括号条件是右括号数必须小于左括号数第三走到长度 2n 时记录答案。只要这三个决策点清楚了代码在任何语言里都能快速写出来。另外我每次复习都会顺手画一遍 n2 的递归树。这个动作看起来简单却能快速唤醒对回溯的直觉比重新读一遍题解有效得多。画完树后再写一遍暴力版和回溯版最后默写一遍 DP 递推整套流程下来不超过 40 分钟但收获比刷三道新题还扎实。还有一个面试时的小技巧如果时间允许可以在写完回溯后主动提一句“这里我用的是 left 和 right 两个状态因为它们同时充当了计数器、剪枝条件和终止条件”。这句话会让面试官觉得你是真的理解了解法的自洽性而不是背代码。括号生成这题本身不难真正拉开差距的就是这些细节表达。希望这份复习笔记能帮你把这题彻底吃透。