很多人第一次看到“【算法三十五】22. 括号生成”这道题时第一反应往往是这不就是一个穷举吗结果打开编辑器写了半天要么答案数量不对要么全是重复组合要么压根不敢提交。我在面试和日常刷题里见过不下十次这道题能一次写对的人确实不多。它表面上叫“括号生成”实际上考的是回溯算法最核心的决策树建模能力同时也是理解卡特兰数、递归剪枝、状态恢复这些概念的绝佳入口。这篇文章我会从题面拆解、暴力解法的局限性、回溯剪枝成型、代码落地的坑再到复杂度分析和面试变体一步步把它讲透。不管你是刚接触回溯算法的新手还是准备面试想查漏补缺的老手都能在这篇里找到能直接用的东西。1. 题面一看就懂但第一次写对的人不到一半1.1 题目到底在问什么题目本身非常简短数字 n 代表生成括号的对数请你设计一个函数生成所有可能的并且有效的括号组合。比如 n 3 时输出应该是((())) (()()) (())() ()(()) ()()()一共 5 个。注意这里有两个关键词一个是“所有”一个是“有效”。如果只是问“有多少种”那是个数学题但题目让你把每一种都列出来这就变成了一道典型的搜索/构造题需要把每条合法路径都完整走一遍。很多初学者会忽略“有效”二字的份量以为只要左右括号数量相等就行结果生成出)(()这种明显不对的串。1.2 直觉解法为什么容易翻车我先说说我见过的高频错误写法。第一种有人把它当成排列组合题先把 2n 个位置看作左右括号的排列生成所有长度为 2n 的括号串再逐个判断是否合法。这种思路没有错但对 n 3 来说总共有 2^6 64 种组合其中合法的只有 5 种n 稍微大一点比如 102^20 已经是 104 万种。更尴尬的是面试官想看的根本不是这个。第二种有人试图“先放完所有左括号再放右括号”这样只能生成一种嵌套结构((...))完全漏掉了()(())、()()()这种并列结构。还有人在循环里用字符串拼接硬凑结果写到一半自己的分支逻辑都理不清。这些翻车案例的共同点是没有意识到括号序列的合法性和“前缀中左右括号的数量关系”强相关。1.3 合法括号序列的核心性质要真正理解这道题必须先记住一个判定规则任意前缀中左括号数量必须大于等于右括号数量且最终两者总数相等。我举个例子看字符串(()())前缀 ( left 1, right 0 前缀 (( left 2, right 0 前缀 (() left 2, right 1 前缀 (()( left 3, right 1 前缀 (()() left 3, right 2 完整串 (()())left 3, right 3每一步前缀里 left 都没小于 right所以它是合法的。反过来看())(走到第三个字符时前缀是())此时 left 1, right 2left 比 right 还少说明这个右括号根本找不到配对的左括号于是判定非法。这个前缀约束就是后面所有回溯剪枝的“法律依据”。2. 为什么“暴力生成再筛选”是下策2.1 组合爆炸的现实感你可以写一个暴力版本练手用递归生成所有长度为 2n 的括号串然后逐个用栈或计数器判断是否合法。跑通很容易n 4 甚至 n 6 都没问题。但一旦 n 变大事情就不妙了。我算笔账n 52^10 1024 种串合法 42 种。n 102^20 1048576 种串合法只有 16796 种。n 152^30 1073741824 种串已经十亿级合法只有 9694845 种。暴力生成的时间开销呈 2^(2n) 爆炸增长而合法结果是卡特兰数 C_n增长速度大约是 4^n / n^(3/2)。两者在 n 小的时候差距还不明显n 越大差距越恐怖。刷题网站里 n 通常给到 8 或 10暴力勉强能过但面试官不会满足于“能过”他要看的是你有没有建模能力。2.2 从“先全生成再判断”到“边生成边判断”关键洞察来了既然合法括号串要求“任意前缀左括号数 ≥ 右括号数”我们完全可以在生成的过程中就把非法分支剪掉根本不需要生成一个完整的串再去判断。这就是“剪枝”二字的含义——筛选逻辑前置到构造过程里。我打个比方。你在一栋楼里找某个房间暴力做法是把每一扇门都推开看一眼不对再关上下一个。剪枝的做法是看到门上挂着“此路不通”的牌子就直接绕过去。递归分支也是一样当剩余右括号数已经少于剩余左括号数时说明当前串前缀已经不合法再往后走必然全错这个分支直接砍掉。2.3 暴力解法不是一无是处说句公道话暴力版本的代码逻辑很直观适合作为理解“合法括号串判定”的辅助练习。我自己当年学这道题的时候就是先写了暴力版然后打印每一步生成结果再自己拿笔勾掉非法分支。这个过程让我真正理解了“为什么回溯剪枝是必要的”而不是觉得“回溯模板背下来就行”。所以我的建议是暴力版一定要写一遍但写完之后要立刻扔掉因为生产环境不会有 n 8 还让你暴力枚举的场景面试题更不会。3. 回溯剪枝成型左右括号计数的决策树3.1 三个关键状态变量回溯算法的本质是在一棵决策树上做深度优先遍历。对于这道题每个节点的状态只需要三个东西剩余左括号数 left剩余右括号数 right当前已经构造的括号串 path每走一步要么放一个左括号要么放一个右括号。终止条件是 left 0 且 right 0这时候把 path 加入答案列表。我习惯用“剩余数量”来定义状态因为终止条件写起来最直观。也有题解用“已用左括号数”和“已用右括号数”两种本质上一样看你喜欢哪种但不要混用尤其不要在一个函数里左边用剩余、右边用已用很容易写出逻辑混乱的 bug。3.2 两条剪枝条件的真正含义用“剩余数量”来表示每一步的选择是这样的如果 left 0可以放一个左括号进入dfs(left - 1, right, path ()。如果 right left可以放一个右括号进入dfs(left, right - 1, path ))。很多新手把第二个条件背成right left却不知道它到底在干什么。我拆开解释一下right是剩余右括号数left是剩余左括号数。如果right left说明当前剩余的右括号比左括号多也就意味着已经使用的左括号数大于已经使用的右括号数。这种情况下再放一个右括号前缀里左括号仍然不少于右括号不会破坏合法性。反过来如果right left说明剩余右括号不多于剩余左括号也就是已用左括号已经不多于已用右括号了。此时再放右括号必然会出现某个前缀里 right 超过 left整个串立刻非法。这个条件的本质是保证“永远不会把右括号放到它配不上的位置”。我每次讲到这里都会用记账来类比左括号是入账右括号是出账任何时刻你已经花出去的钱不能超过你已经收到的钱。剩余right left的意思是账上还“欠着”左括号额度这时候再记一笔右括号支出才是安全的。3.3 手绘 n 2 的决策树为了把整个过程落到直觉上我带大家走一遍 n 2 的递归过程。初始状态left 2, right 2, path 空串。第一步left 0成立可以放左括号进入状态left1, right2, path(。注意此时right left2 1也成立但递归的顺序是先看左括号分支所以先走放左括号。当前状态left1, right2, path(如果放左括号进入left0, right2, path((。此时left0不能放左括号只剩右括号可放依次放两个右括号得到(())。如果放右括号进入left1, right1, path()。此时left1可放左括号right left1 1 不成立不能放右括号所以只能放左括号得到()(再放一个右括号得到()()。回到第一步的另一个可能如果第一步直接放右括号进入left2, right1, path)。此时检查right left1 2 不成立因此这个分支直接不存在。也就是说根节点的右括号分支在第一时间被剪掉。最终结果只有两种(())和()()。和卡特兰数 C_2 2 完全吻合。我强烈建议读者把 n 3 的递归树也自己画一遍画完你对剪枝时机、回溯顺序、结果顺序会有一个质变级的理解。4. 代码落地三种语言版本和最容易踩的坑4.1 Python 版本不可变字符串省心Python 里我首选字符串拼接的方式因为字符串是不可变对象函数传参时相当于拷贝了一份天然不存在“回溯恢复”的问题。from typing import List def generateParenthesis(n: int) - List[str]: res [] def dfs(left: int, right: int, path: str): if left 0 and right 0: res.append(path) return if left 0: dfs(left - 1, right, path () if right left: dfs(left, right - 1, path )) dfs(n, n, ) return res这里path (会生成一个新字符串不会修改原来的 path所以递归返回后不需要做任何清理操作。这也是 Python 写回溯题最舒服的地方——如果你用List[str]当 path在 append 结果的时候必须写.join(path)千万别忘。4.2 Java 版本StringBuilder 必须手动回溯Java 里如果图方便用String path也可以但高频写法是StringBuilder sb因为它修改成本低。代价是递归返回后必须手动删除刚加的字符否则同一个StringBuilder对象会在兄弟分支之间互相污染。class Solution { public ListString generateParenthesis(int n) { ListString res new ArrayList(); dfs(n, n, new StringBuilder(), res); return res; } private void dfs(int left, int right, StringBuilder sb, ListString res) { if (left 0 right 0) { res.add(sb.toString()); return; } if (left 0) { sb.append((); dfs(left - 1, right, sb, res); sb.deleteCharAt(sb.length() - 1); } if (right left) { sb.append()); dfs(left, right - 1, sb, res); sb.deleteCharAt(sb.length() - 1); } } }这条deleteCharAt(sb.length() - 1)就是回溯里常说的“状态恢复”。如果漏掉你会发现 n 2 时输出变成(())、(())这种重复结果或者出现(()这种残缺串因为上一个分支留下的字符没有清掉。C 版本几乎一样把deleteCharAt换成pop_back即可。4.3 剪枝条件的边界要小心初学者最容易在第二个分支上写出if (right 0)这会导致大量非法串混入结果。正确条件是right left不是right 0。为什么因为即使还剩右括号也必须保证放下去之后前缀仍然合法。right left实际上是在问“当前剩余的右括号比左括号多吗”等价于“我已经用了足够的左括号来支撑这次放右括号吗”。另外一个边界是 n 0。LeetCode 里 n 从 1 开始但如果你自己扩展应考虑 n 0 时返回[]还是[]。从数学上空串是合法的空括号组合所以返回[]更严谨。4.4 测试用例怎么设计才靠谱我每次写完这道题至少会跑这几组n 1期望输出[()]检查递归能不能正确结束。n 2期望[(()), ()()]数量是 2重点检查有没有重复和漏项。n 3期望 5 个顺序无关集合相等即可。n 8数量应该是 1430用集合长度验证顺便感受一下卡特兰数的增长。5. 复杂度与卡特兰数答好这道题的“加分项”5.1 时间复杂度为什么不是 2^(2n)面试官问复杂度你要是干巴巴说“O(2 的 2n 次方)”会给面试官留下“你只是背了模板”的印象。这道题的正确回答是回溯只遍历合法分支所以生成每种结果的时间是 O(n)而合法结果数是第 n 个卡特兰数 C_n因此总时间复杂度是O(n * C_n)。卡特兰数的渐近展开是C_n ~ 4^n / (n^(3/2) * sqrt(pi))代入后总体复杂度近似 O(4^n / sqrt(n))。相比暴力的 O(2^(2n)) O(4^n)少了整整一个 sqrt(n) 因子而且 n 越大优势越明显。这个推导不需要在面试里完整给出但能说出“卡特兰数”三个字并且知道它和 4^n 的关系已经能甩开一大批只会背代码的候选人了。5.2 空间复杂度递归深度最多是 2n走一条最深的嵌套路径(((...)))所以递归栈的空间是 O(n)。如果结果集不计入这就是答案。如果计入结果集每个结果长度是 2n共 C_n 个那结果集本身占用 O(n * C_n)但通常面试中会先说明“先不算存储答案的空间”。5.3 卡特兰数到底是什么卡特兰数是个很美的组合数学序列前几项是1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...它的递推公式是C_0 1 C_n sum_{i0}^{n-1} C_i * C_{n-1-i}这个序列会出现在一堆看起来毫不相关的问题里n 对括号的合法括号序列数n 个节点的二叉树形态数n 个元素入栈出栈的合法出栈顺序数n × n 方格中从左下到右上且不越过对角线的路径数凸 n 边形的三角剖分数如果你能主动把这些关联讲出来面试官会认为你不仅会做题而且做过系统的知识串联。这比多刷十道简单题更有用。5.4 关于“能否再优化”偶尔会遇到追问“复杂度能不能再低”我的回答是因为题目要求输出所有合法组合而组合数量本身就是卡特兰数级别所以任何算法都至少要遍历并输出这么多结果下界就在那里。回溯已经是最贴合问题本质的解法不存在数量级上更优的通用做法。如果题目改成“只求数量”那当然直接用卡特兰数公式或者 DP那又是另一道题了。6. 面试官真正的考点这道题怎么答才稳6.1 先判断一个括号串是否合法括号生成和括号合法性判断是一对“对偶题”。我面试别人的时候经常先问“给你一个字符串怎么判断它是否合法”再问“如果让你生成呢”。前者用栈或者计数器就能搞定def is_valid(s: str) - bool: count 0 for ch in s: if ch (: count 1 else: count - 1 if count 0: return False return count 0基于计数器的方法比栈更轻量而且它和生成过程里的剪枝条件是同一套逻辑任意时刻左括号数不小于右括号数。能把这两个方向打通说明你真的理解了括号序列的结构而不是背了两段代码。6.2 变体只求数量时怎么办如果题目改成“n 对括号一共有多少种合法组合”回溯就会显得笨重。此时直接用 DP 或卡特兰数dp[0] 1 dp[i] sum_{j0}^{i-1} dp[j] * dp[i-1-j]dp[i] 的含义是第 i 对括号的合法数量等于固定最外层左边一个左括号和右边一个右括号后中间放 j 对、右边放 i-1-j 对的乘积之和。这个思路比背诵公式更利于白板推导也更容易和面试官交流。6.3 变体出栈顺序与二叉树形态我聊一个常被作为“彩蛋”的延伸点。把左括号看成入栈右括号看成出栈那么每一个合法括号串都可以对应一组入栈出栈操作的顺序。换句话说n 个元素的合法出栈序列数量也是卡特兰数 C_n。更进一步n 个节点的二叉树的中序遍历形态数也是 C_n。这三者之间其实存在同构关系理解了括号生成等于顺手理解了出栈序列和二叉树形态计数的核心结构。6.4 我在面试中的实操建议最后说点面试表现层面的东西。我作为面试官见过很多人一上来就埋头写代码这其实不是最优策略。我的建议是先和面试官确认 n 的范围确保你不会漏掉边界条件。用一两句话说出思路“用回溯每次选择放左括号还是右括号放右括号时要求剩余右括号大于剩余左括号保证前缀合法。”在白板上画一个 n 2 的决策树让面试官看到你已经梳理清楚分支。写完代码主动跑一个 n 3 的例子口头追踪前两个分支证明代码能跑通。主动提一句复杂度是 O(n * C_n)并且说明结果集空间不算。这套流程下来即便代码有小瑕疵面试官也更容易给出“思路清楚基础扎实”的评价。回到这道题本身我个人刷题的经验是所有回溯相关的题目核心都在“决策树怎么画”和“剪枝条件怎么定”。括号生成是少有的、剪枝条件完全由数学性质决定的题目把这道题吃透再去做组合总和、全排列、N 皇后你会发现它们的套路惊人的一致——都是在一个多阶段决策的树上做深度优先遍历只是每个阶段的可选项和合法性条件不同。这也是我把它当作回溯算法入门第一课的原因。
