聊到LeetCode刷题有两道题我觉得特别适合放在一起讲第20题“有效的括号”和第22题“括号生成”。一个要求你判断一段括号字符串合不合法一个要求你把n对括号的所有合法组合全部枚举出来。前者是经典的栈应用后者是回溯算法的入门必刷题两道题都围绕“括号匹配”这个核心规则展开刷起来有一种天然的递进感。如果你刚开始刷题或者面试前想快速过一遍基础算法这对组合很值得花上一个晚上认真研究。题目本身不难但背后牵扯到的数据结构选型、递归状态设计、复杂度分析都是面试里容易追问的地方。这篇文章我就从实际刷题和面试复盘的角度把这两道题的思路、代码、坑位以及延伸方法完整拆一遍尽量做到看完就能上手写。我先把结论放在前面20题表面是栈的应用本质是对“括号合法性判定规则”的逐字符模拟22题表面是回溯枚举本质是利用同一条合法性规则在递归过程中做剪枝。理解这一条线比单纯背解题模板重要得多。1. 先搞懂这两道题为什么要放一起刷1.1 从“判断”到“生成”正好是一个闭环“有效的括号”这道题通常会给出一个只包含(、)、[、]、{、}的字符串问它是否合法。题目的合法定义有三条左括号必须有相同类型的右括号闭合闭合顺序必须正确括号类型不能交叉。这个定义看上去简单但不少人写代码时会把“类型相同”和“顺序正确”搞混比如([)]这种串左右括号数量是对的类型也算齐全可顺序完全错乱一提交就会暴露问题。如果把所有合法括号串看成一个集合20题做的就是成员判断给我一个候选串判断它在不在集合里。22题做的则是集合枚举把所有长度为2n的合法串全部列出来。这两个方向听起来不同实际用的是同一条规则只是反着用。先做判断再做生成等于先理解了游戏规则再去写一个遵守规则的程序这样理解起来会顺很多。我实际刷题时的一个体会是如果先做20题再立刻做22题你会在写第二个题的时候突然意识到很多细节其实是“换汤不换药”。比如22题里经常用到的剪枝条件right left翻译成人类语言就是“当前右括号的数量不能超过左括号的数量”这正好对应20题里“必须以正确顺序闭合”的要求。这种顿悟感是拆开来单刷两道题体会不到的。1.2 两道题共同的核心能力从能力模型上看20题对应的是栈和哈希映射这两个基础数据结构的使用。遇到需要“最近的”“嵌套的”“成对消除的”场景栈几乎是天然答案比如表达式求值、HTML标签闭合解析、函数调用栈等底层都是同一个模型。22题对应的是递归加回溯这个算法框架重点在于状态怎么定义、分支怎么选、无效分支怎么剪。这两组能力在LeetCode里出镜率极高。二叉树遍历有递归的影子排列组合是回溯的典型应用岛屿类问题本质上也是在网格里做DFS搜索。所以把这两道题放一起刷其实是用最少的时间覆盖两组高频考点而且两道题难度适中不至于一上来就把人劝退。2. LeetCode 20 有效的括号用栈和哈希表搞定匹配判断2.1 最直觉的解法右括号映射左括号 栈先说思路。维护一个栈从左到右扫描字符串。遇到左括号就压栈遇到右括号就检查栈顶元素是否是对应的左括号如果匹配就弹出不匹配直接返回False。扫描结束后如果栈为空说明全部匹配成功否则说明有左括号没有被闭合也返回False。Python代码写出来是这样class Solution: def isValid(self, s: str) - bool: pairs {): (, ]: [, }: {} stack [] for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack这里有两个细节值得展开说。第一用字典保存右括号到左括号的映射比写一长串if-elif要清爽得多而且以后如果增加新的括号类型只需要在字典里加一项代码逻辑完全不用动。第二判断右括号时必须先确认栈非空否则直接取栈顶会报错。很多人第一次写会漏掉这个判空结果输入一上来就是右括号时直接越界这个错误在LeetCode的用例里一定会被扣分。时间复杂度是O(n)只需要遍历一次字符串空间复杂度是O(n)最坏情况下字符串全是左括号栈里会存下所有字符。2.2 三个最容易踩的坑第一个坑是“只数数量不验证位置”。有一种错误解法是分别统计三种括号的数量只要左右数量相等就认为是合法的。这个思路在只有一种括号的时候还能勉强用一旦出现多种括号就废了。比如([)]三种括号数量都对称但它并不合法因为[在(后面却先被)闭合了。正确做法必须用栈来维护“最近一个未匹配的左括号”这样才能确保闭合顺序正确。第二个坑是“遇到右括号直接弹栈但没有判空”。当输入以右括号开头时比如)(第一次循环就走到了弹栈分支此时栈是空的系统直接报错。所以在处理右括号前必须先判断if not stack这不只是为了防报错它本身就是一种非法情况没有任何左括号在等待匹配右括号却先出现了。第三个坑是“循环结束后忘了检查栈是否为空”。比如(()遍历完三个字符后栈里还留着一个(说明有一个左括号没有被闭合这个字符串不合法。所以最终返回值必须是not stack而不是直接返回True。这个错误我在代码评审里见过很多次属于看起来逻辑完整、一提交就被用例打脸的类型。2.3 边界Case与小优化有一个很基础但有效的优化是如果字符串长度是奇数直接返回False。因为合法括号串的长度必然是偶数这个判断能帮你跳过一整轮扫描虽然复杂度不变但实测响应会快一些。另一个小细节是判断ch in pairs时实际上是在判断字符是否是右括号因为字典的key只有右括号如果字符串中可能出现其他字符需要额外处理但这题里不会。另外补充一个思路有人会用“不断替换空括号对”来解题也就是每遇到()、[]、{}就替换成空字符串直到不能再替换为止最后看字符串是否为空的。这个办法很直观但最坏情况下时间复杂度是O(n^2)因为每次替换都要扫描一轮字符串。面试时可以作为思路补充提一句但别把它当主解法栈的方案才是这个问题的标准答案。3. LeetCode 22 括号生成用回溯枚举所有合法组合3.1 从暴力枚举到回溯的思路变化拿到22题最朴素的想法是生成所有长度为2n的括号字符串再逐个用20题的合法性判断去筛选。这个思路在n很小的时候看起来很合理但复杂度完全撑不住。长度为2n每个位置可以选左括号或右括号总共有2^(2n)种可能就算过滤掉左右数量不对的合法候选数量也有C(2n, n)当n15时已经超过1.5亿逐一判断完全不现实。回溯的思路是在生成过程中就保证局部合法性。每一步选择加左括号还是右括号之前先检查一下这个选择会不会让字符串变得不合法如果会就直接放弃这个分支。这样做会剪掉大量无效路径我们只需要沿着“合法前缀”往下走最后得到的一定都是合法结果。这个思路其实很像现实生活中走迷宫与其把所有死路都走一遍再回头不如在每个岔路口就看看哪条路明显是死胡同直接绕开。回溯算法里的“剪枝”干的就是这件事。3.2 递归状态与剪枝条件递归函数的状态非常简单只需要三个信息当前已经构造的字符串cur、当前使用了多少个左括号left、当前使用了多少个右括号right。每次递归有两个可选动作加一个左括号或者加一个右括号。但这两个动作并不是任何时候都能做。加左括号的前提是left n不然左括号配额用完了。加右括号的前提是right left即右括号数量不能超过左括号数量否则就会出现某个前缀里右括号数量多于左括号的非法情况。当len(cur) 2 * n时说明左右括号都用完了当前字符串就是一个合法结果记录并返回。代码实现class Solution: def generateParenthesis(self, n: int) - List[str]: res [] def backtrack(cur: str, left: int, right: int) - None: if len(cur) 2 * n: res.append(cur) return if left n: backtrack(cur (, left 1, right) if right left: backtrack(cur ), left, right 1) backtrack(, 0, 0) return res这段代码非常短但核心逻辑很密。你可以把cur理解成“当前走过的路径”left和right是路径的状态值两个if就是剪枝条件终止条件是路径长度到达目标值。这是回溯算法的标准模板后面做排列、组合、子集等问题时你会发现代码骨架几乎一模一样。如果用列表来记录当前路径可以写成更贴近通用回溯模板的形式class Solution: def generateParenthesis(self, n: int) - List[str]: res [] path [] def backtrack(left: int, right: int) - None: if len(path) 2 * n: res.append(.join(path)) return if left n: path.append(() backtrack(left 1, right) path.pop() if right left: path.append()) backtrack(left, right 1) path.pop() backtrack(0, 0) return res两种写法思路完全一致第二种更接近以后刷题时常见的“路径 选择 撤销”模板建议优先熟悉这种写法。字符串拼接虽然直观但每次递归都会产生新的字符串对象在处理大规模组合时会白白增加不少内存操作。3.3 递归树与卡特兰数我们用n2来演示一下递归树。根节点是空字符串状态是(left0, right0)。第一层只能加左括号得到(状态变成(1,0)。第二层有两个分支加左括号得到((状态(2,0)加右括号得到()状态(1,1)。从((继续此时left已经等于2不能再加左括号只能加右括号得到(()状态(2,1)再加一个右括号变成(())状态(2,2)结束。从()继续left还小于2可以加左括号得到()(状态(2,1)再加右括号得到()()结束。最终结果是[(()), ()()]。从这棵树里可以看到剪枝的作用当left n时左分支被砍掉当right left时右分支被砍掉。很多无效路径在很浅的层级就被终止了所以整个递归树的规模比C(2n,n)小得多。合法括号串的数量是一个经典的组合数学结论它等于第n个卡特兰数C_n (1 / (n1)) * C(2n, n)n1时结果是1n2时结果是2n3时结果是5n4时结果是14。刷题时很多人的复杂度分析只写一句“指数级”这在面试里不够用能直接说出卡特兰数公式、并解释它为什么会出现在这里会显得你对组合计数有概念。为什么是卡特兰数因为“合法括号串的数量”和“栈的出栈序列数量”在数学上是同一个计数对象。把左括号看成入栈右括号看成出栈合法括号串对应着合法的入栈出栈序列。这类组合对象还有二分查找树形态数量等看到卡特兰数时可以顺带联想一下理解会更深。3.4 换一种视角与出栈序列的关联如果你之前做过“给定入栈序列判断某个出栈序列是否合法”这类问题会发现它和括号匹配几乎是同一件事。入栈记作左括号出栈记作右括号那么在任意时刻出栈次数都不能大于入栈次数否则就是“栈空了还要弹出”对应到括号串里就是“右括号多于左括号”。这种跨题目的类比看一遍可能不觉得有什么但见得多了会发现LeetCode很多题都是同一套底层模型换壳。括号匹配、出栈序列、二叉树遍历顺序、DFS括号化表示它们共享的数学结构正是卡特兰数的来源。记住这个点以后看到“n对括号”“n个元素入栈出栈”这类描述时第一反应就不会是死记公式而是自然想到用卡特兰数去估算结果规模。4. 刷完这两道题之后可以顺带做的事4.1 我建议的练习节奏如果你打算按这个组合来刷我建议你给自己留足一个完整的时间块大概一到两小时。第一步用5到10分钟读题并独立思考第20题不要急着看题解第二步写代码并提交重点关注三个边界空栈遇到右括号、结束后栈非空、多种括号交叉出现第三步进入第22题先在纸上画出n2或n3的递归树再写回溯代码第四步提交之后比对判断标准在两题之间是如何映射的。我自己试过这个节奏最花时间的其实不是写代码而是第22题的递归树。只要能把n3的树画明白剪枝条件right left为什么存在、为什么足够就都清楚了。画完之后再写代码基本一遍过。有一点要提醒不要一上来就追求最优写法。第20题可以先写一个用三个计数器的版本然后自己试着用测试用例击穿它再切换到栈解法。这个过程比直接抄标准答案更能加深印象。第22题同理先写一个暴力枚举所有排列再筛选的版本跑一下n4看看有多慢你自然会体会到回溯剪枝的价值。4.2 括号类题目的延伸记忆地图做完这两题可以顺带扩展几道常见的括号题形成一个小的记忆地图。这里列几个我实际刷过、觉得和这两题关联密切的题目核心考点和这两题的关系921. 使括号有效的最少添加贪心 / 遍历计数用计数判断合法性的直接应用难度低1249. 移除无效的括号栈 标记删除从不合法串里找出需要删除的括号位置678. 有效的括号字符串双变量 / 双栈在括号基础上加入通配符*判断条件更复杂32. 最长有效括号栈 / 动态规划从“全串是否合法”变成“找最长合法子串”241. 为运算表达式设计优先级分治 / 递归生成类问题里拆分左右子问题的思路这些题不一定都要立刻刷但看完这张表你可以发现一个规律括号题的底层都是“合法性规则 某种遍历方式”。20题教会你怎么判断22题教会你怎么生成遇到其他变体时你只需要问自己一句话它是在判断、生成还是在最优化某个括号状态。想清楚这个方向选数据结构的思路就有了。4.3 面试现场被追问时的应对思路面试和刷题最大的区别是面试官一定会追问。20题最常见的追问是“这个题不用栈能用别的办法吗”这时候如果你直接说不行印象分会打折。更好的回答是分场景如果字符串只有一种括号比如只有(和)那确实不用栈用一个计数器就能搞定——遇到(加一遇到)减一任何时候不能为负数最后必须归零。但题目里有三种括号就必须用栈来记录类型和顺序。这种回答既展示了原理理解又覆盖了变体。22题最常见的追问是“除了回溯还有别的解法吗”你可以提动态规划。思路是把“生成n对括号”拆成外层有一对括号括号内部放k对括号外部放n-1-k对括号。于是有递推式f(n) sum(f(k) * f(n-1-k))。这个递推式本身就是卡特兰数的递推形式。提到这一步面试官通常就满意了不需要现场写出完整DP代码。还有一个小经验面试时讲回溯题一定要把“撤销选择”这一步讲清楚。很多人代码写对了但被问“你为什么要pop()”时答不上来。这里的本质原因是递归回到上一层后需要恢复现场让当前路径变回进入分支前的状态否则下一次分支会在错误的基础上继续拼接。把这个逻辑讲透比背十篇题解都有用。4.4 一点个人体会这两道题我刷过很多次每次准备面试前都会重新写一遍。不是因为它们难而是因为它们足够基础能快速检查我对栈、哈希映射、递归、回溯这几个概念的熟练度。如果15分钟内能无Bug写完两题并且把复杂度、卡特兰数、剪枝条件讲清楚我对当天的算法状态就会比较有底。最后分享一个小技巧把20题和22题当成一组“互逆题”来复习。复习的时候不要先看代码而是先自己复述一遍“合法括号串”的判定标准——从左到右扫描左括号出现次数永远不少于右括号出现次数最终两者相等。然后问自己如果用这个标准去判断怎么写如果用这个标准去生成怎么剪枝这两个问题如果能自然回答出来说明你是真的理解了而不是背住了答案。