刚把代码随想录回溯篇刷到第四篇说实话这个节点才是真正开始豁然开朗的地方。前几篇你还在跟组合、分割字符串较劲到了这一篇题目突然变成N皇后、解数独、复原IP地址、单词搜索这些“看起来就头大”的经典题。但它们本质上仍然是同一个东西递归穷举 状态重置 剪枝。这篇就结合我自己的刷题过程把回溯篇四涉及的题型、模板、易错点、调试方法都拆开聊一遍顺便回答一个很多人问过的问题算法回溯和程序崩溃时的栈回溯到底是不是一回事。如果你是正在按代码随想录刷题的人或者刚把回溯基础部分看完、想进阶到棋盘类和字符串类回溯题又或者单纯想搞明白回溯算法怎么写才不出 bug这篇文章都值得你花十分钟读完。只是建议你手上备好编辑器看到代码就自己敲一遍刷题这件事光看是不顶用的。1. 回溯篇四到底在讲什么从组合问题进阶到棋盘与穷举1.1 回溯算法能解决哪几类问题先建立一个整体图谱我刷题这么久发现回溯算法最喜欢“考试”的场景就四类组合、排列、子集、分割再加上一个棋盘/网格搜索。代码随想录回溯篇的安排也是按这个顺序走的前几篇解决组合总和、全排列、子集、分割回文串到了第四篇基本就是棋盘问题和字符串穷举问题的天下了。这样说可能会让新手有点懵我先把回溯题的类型地图画出来题型代表题核心特征组合类组合总和、组合总和II、电话号码字母组合顺序无关通常需要startIndex控制下一次搜索起点排列类全排列、全排列II顺序有关每一层都要从头开始选需要用used数组标记已选子集类子集、子集II、递增子序列收集所有节点而不是只收集叶子每次递归前都记录结果分割类分割回文串、复原IP地址对字符串进行切片需要处理子串合法性棋盘类N皇后、解数独二维递归一层递归管一行/一格状态往往是一个棋盘图/网格类单词搜索、岛屿问题DFS在网格中移动用标记数组防止走回头路回溯篇四基本就是最后三类的集中轰炸。这类题有个共同特点直接暴力循环写不干净你必须让程序有“尝试错误、回退再试”的能力。如果不提前把模板和状态重置想明白很容易写出“运行结果莫名多出很多重复结果”或者“剪枝一多就漏解”的代码。1.2 为什么搞懂回溯之后其他算法题也会变简单很多人觉得回溯就是背模板其实不是。回溯和二叉树遍历、图论DFS、动态规划、甚至是程序调试里的栈回溯底层都是同一套思维递归地进入某个状态判断这个状态行不行不行就退回上一个状态重新选。举个很直观的例子你在一个没有标记的森林里找宝藏走一条路发现是死胡同你会退回到上一个岔路口换另一条路。这个“退回上一步”的动作就是回溯。算法题里的回溯不过是把这个动作写成代码递归调用前修改状态递归返回后撤销修改。你代码里那几行path.pop()就是在模拟“从死胡同退回到岔路口”。所以我一直觉得刷回溯题最大的收获不是会做几道题而是真正理解了递归是怎么一层层展开、又一层层收回的。有了这个感觉再看深度优先遍历、动态规划的状态转移、甚至复杂的搜索题都会顺畅很多。2. 回溯的“万能模板”与状态重置原理2.1 一个模板打天下递归四要素代码随想录里的回溯模板我默写了不下二十遍最后发现模板可以浓缩成四句话确定递归函数参数、确定终止条件、遍历本层所有选择、撤销选择。用Python写基本形态是这样的def backtrack(路径, 选择列表): if 满足终止条件: 记录答案 return for 选择 in 选择列表: 做选择 # 修改路径和状态比如 path.append(x), used[i] True backtrack(路径, 新的选择列表) 撤销选择 # path.pop(), used[i] False这里最关键的其实是“撤销选择”。很多人第一遍刷题时都会犯同一个错递归进去能走到正确答案但返回上一层时忘记把状态改回去结果整个路径越走越奇怪。你只有理解了“递归返回后必须恢复现场”才算真正理解回溯。还有个细节需要提醒终止条件要写得够具体。比如求子集时庆祝“每一层递归进入时都记录当前路径”而求排列时则是在len(path) len(nums)时记录。终止条件写错通常会多出很多空结果或者重复结果。2.2 状态重置为什么有的代码要pop有的不用pop初学者最容易困惑的一个点是为什么组合题的代码里有startIndex但不用used数组排列题却必须用used数组组合和排列的本质区别就是“顺序是否重要”。组合要避免选到重复组合所以每一层递归都从startIndex开始保证下一次选的元素都排在当前元素后面例如for i in range(startIndex, len(candidates)): path.append(candidates[i]) backtrack(i 1, path, ...) # 不回头 path.pop()排列则不同[1,2]和[2,1]是两个结果。因此每一层递归都必须从头把数组扫一遍但已经用过的元素不能再用于是需要used[i]来标记for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) backtrack(path, used) path.pop() used[i] False这里需要特别注意的是只要是修改了外部状态就一定要在递归返回后恢复。比如棋盘类题目里把某个格子从.改成Q递归之后一定要再改回.。如果你用的是“局部拷贝”而不是“修改再恢复”那也可以但效率会差很多。比如path [nums[i]]这种写法每次递归都会创建新列表虽然写起来简单但大数组时会有大量内存分配。刷题时为了性能我还是更推荐在同一个列表里append/pop配合状态数组完成重置。2.3 剪枝的艺术从超时到AC往往就差一行判断回溯算法最被人诟病的就是暴力穷举指数复杂度。但加了剪枝之后很多题完全跑得动。剪枝不是玄学本质就是把已经不可能产生正确结果的分支提前砍掉。拿“组合总和II”举例如果数组里有重复数字而且每个数字只能用一次题目要求结果不能有重复组合。这里有两个剪枝层排序后如果candidates[i] ...已经超过目标值可以提前break。同一层递归中如果当前元素和前一个元素相同且前一个元素在当前层已经处理过就跳过当前元素。第二种“树层去重”是很多人的噩梦。举个例子数组是[1,1,2,4]目标值是5。第一层选了第一个1第二层再选第二个1最后组合是[1,4]但如果第一层直接选第二个1第二层就没有别的前面元素可以配合了照样会生成[1,4]从而重复。要避免这种重复常见做法是排序后判断i startIndex and candidates[i] candidates[i-1]时直接continue。这里必须用i startIndex而不是i 0因为同一路径上不同层的重复元素是允许的只有同一层内不能重复选。我自己的经验是遇到去重先画一棵递归树标出哪些节点属于同一层哪些属于不同层。树画清楚了代码就写对了。这就是代码随想录里反复强调的“树层去重”和“树枝去重”。3. 回溯篇四的经典题目实战拆解N皇后、解数独、复原IP地址、单词搜索3.1 N皇后用三个数组做列和对角线去重N皇后是回溯篇四里地位极高的一道题。问题很简单在N行N列的棋盘上摆N个皇后让它们彼此不能攻击即任意两个皇后不能在同一行、同一列、同一条对角线。代码实现思路一行一行放皇后用一个row参数记录当前处理到第几行然后遍历当前行的每一列检查该列是否安全。安全性检查可以写成函数也可以优化成三个布尔数组col[j]表示第j列是否已经被占用dia1[row j]表示从左下到右上的那组对角线是否被占用行和列之和是定值dia2[row - j n - 1]表示从左上到右下的那组对角线是否被占用行和列之差是定值加偏移避免负数。Python参考代码def solveNQueens(n): res [] board [[.] * n for _ in range(n)] col [False] * n dia1 [False] * (2 * n - 1) dia2 [False] * (2 * n - 1) def backtrack(row): if row n: res.append([.join(r) for r in board]) return for j in range(n): if col[j] or dia1[row j] or dia2[row - j n - 1]: continue board[row][j] Q col[j] dia1[row j] dia2[row - j n - 1] True backtrack(row 1) board[row][j] . col[j] dia1[row j] dia2[row - j n - 1] False backtrack(0) return res这里最有意思的点是“为什么用行和列相加/相减来代表斜线”左下到右上的斜线上所有格子的行列是同一个值左上到右下的斜线上所有格子的行-列是同一个值。所以不需要每次去检查整个对角线有没有皇后一个数组就能搞定。N皇后几乎是测试你是否真正理解状态重置的试金石因为每次递归返回都要把棋盘和三个标记数组全部复位少一行都会出诡异结果。3.2 解数独二维递归中的暴力美学解数独是回溯篇四另一座大山。它的特殊性在于递归不是一个一个处理一维数组元素而是要在9x9的棋盘上找到空位逐个尝试1到9。这就涉及“二维递归”的写法。常规思路是这样的外层函数找到一个空格内层循环尝试把1到9填进去填下之前检查是否满足行、列、九宫格约束如果满足就递归继续填下一个空格如果后续递归失败就撤销当前填入的数字继续尝试下一个数字如果9个数字都试完还是不行就返回False让上一层重新选择。这里返回True/False的写法往往比void型更好用因为你一旦找到一种可行解就可以立即层层返回不需要继续穷举。参考代码片段def solveSudoku(board): def valid(r, c, ch): for i in range(9): if board[r][i] ch: return False if board[i][c] ch: return False if board[3 * (r // 3) i // 3][3 * (c // 3) i % 3] ch: return False return True def dfs(): for i in range(9): for j in range(9): if board[i][j] .: for ch in 123456789: if valid(i, j, ch): board[i][j] ch if dfs(): return True board[i][j] . return False # 9个数字都不行 return True # 没有空格了 dfs()你会发现写完解数独之后N皇后突然变得很简单因为N皇后只是每一行选一个位置而数独每个空位都有9种可能。但它们的核心结构完全一致尝试、递归、撤销。有几个容易写错的细节九宫格下标3 * (r // 3) i // 3和3 * (c // 3) i % 3很多人第一次写不出来。推导逻辑是先根据当前行r定位到所在宫格的第一行3 * (r // 3)然后加上i // 3得到宫格内第几行列同理。实在记不住就自己画一个9宫格坐标图对照着写。3.3 复原IP地址字符串切割回溯的边界问题复原IP地址和分割回文串是同一类题但IP地址的合法性判定要求更严格地址由四段组成每段在0到255之间而且不能有前导零比如01.2.3.4不合法。切割的时候用startIndex表示当前处理到字符串的哪个位置用dotCount记录已经加了多少个点。很多人的第一版代码会写成先取出一个子串判断合法然后加一个点递归最后再删掉点。这没问题但有一个陷阱s[start:i1]如果长度大于3肯定不合法直接break如果等于0可以单独存在但00、01都不行。同时终止条件不是简单字符串用完就行而是“已经切成四段且字符串用完”。所以更清晰的状态记录方式是用一个path列表保存每一段的字符串最后再..join(path)。参考思路def restoreIpAddresses(s): res [] def backtrack(start, path): if len(path) 4: if start len(s): res.append(..join(path)) return if start len(s): return if s[start] 0: # 只能单独成一个段 backtrack(start 1, path [0]) return for end in range(start, min(start 3, len(s))): seg s[start:end 1] if int(seg) 255: continue backtrack(end 1, path [seg]) backtrack(0, []) return res这里我用的是path [seg]而不是append/pop因为字符串分段问题用不可变路径写法反而更少出错。这也印证了前面说的状态重置不是非得手动pop只要你保证传入下一层的路径是“新状态”不污染外部变量一样是正确的回溯。只是在性能要求高的时候同样建议改写为append/pop。3.4 单词搜索棋盘上的DFS与状态重置单词搜索Word Search虽然不常在回溯篇正篇里出现但我刷第四篇时经常和N皇后一起练因为它完美体现了“网格搜索状态重置”给你一个字母矩阵判断一个单词是否存在于相邻格子的连续路径中。核心逻辑是从每个格子出发如果首字母匹配就向上下左右四个方向搜索下一个字符走过的格子要标记为已访问搜索完要恢复标记。def exist(board, word): m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] def dfs(i, j, k): if k len(word): return True if not (0 i m and 0 j n): return False if visited[i][j] or board[i][j] ! word[k]: return False visited[i][j] True for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)): if dfs(i di, j dj, k 1): return True visited[i][j] False return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这里最容易错的是visited标记的位置。如果你在进入递归后没有立刻标记而是先判断条件再标记那么同一个格子可能被当前路径重复访问。另外剪枝技巧还有基于前缀的优化如果当前剩余字符长度已经大于剩余可走格子数可以提前返回但这道题一般不会卡那么狠。刷到这里你会发现棋盘类回溯题跟前面组合类最大的区别是组合题的“选择列表”是一个数字列表棋盘题的“选择列表”是坐标。一旦你能熟练把“坐标上的选择与撤销”写顺网格搜索和N皇后就都不难了。4. 刷题环境与工具链如何高效完成oj刷题和python题库刷题训练4.1 语言选择与刷题习惯我用Python刷题的理由现在很多刷题网站都支持Python。我自己的主力语言也是Python原因很直接写回溯题时Python的列表推导、切片、.join()这类操作能让逻辑非常清晰。比如恢复IP地址里..join(path)一行搞定字符串拼装用C就要多写好几行。当然不是说C/Java不好。如果你目标公司面试以C为主我建议你至少用C把每个题过一遍因为面试官可能会要求你用指定语言写。Python刷题的好处是“快速验证思路”坏处是手写细节容易被语言特性掩盖。我的习惯是平时用Python刷面试前两周把高频题每道都用Java或C再写一遍。刷题网站的选择也比较透明力扣就是最常用的题型全、讨论区质量高牛客网适合笔试模拟Codeforces、AtCoder适合打竞赛。对于跟着代码随想录刷的人来说力扣足够因为代码随想录里的题号基本都对应力扣原题。4.2 从代码随想录到labuladong刷题笔记怎么搭配使用很多人在评论区问代码随想录和labuladong的刷题笔记到底选哪个我的看法是两者不冲突。代码随想录的好处是“刷题路线固定”每一章告诉你先做哪些题再做哪些题特别适合不知道怎么安排顺序的人。labuladong则更侧重“算法框架”比如他反复强调的回溯算法是“多叉树的遍历”和代码随想录里的模板其实殊途同归。我自己使用的策略是主线按代码随想录的题目顺序刷卡壳的时候去看labuladong对同一类题的框架总结。比如我刷N皇后之前就在labuladong的笔记里看到一句话回溯算法就是“路径 选择列表 结束条件”。这句话和代码随想录的模板互相印证双倍加深记忆。但是我不建议两种资料同时从头通读否则你会陷入“今天看这个明天看那个”的混乱。更好的做法是选一套作为主线另一套作为参考字典。看到某个知识点不懂再打开另一套书签找到对应章节。4.3 力扣刷题攻略题号顺序、难度控制和AC标准代码随想录回溯篇四的题号区间大致集中在37、51、52、79、93、131、332这类题号上。我建议按“从易到难”重新排序刷先做复原IP地址93、分割回文串131再做N皇后51、解数独37最后再做重新安排行程332和单词搜索79。因为前两个纯粹是字符串切分不涉及二维坐标的抽象适合作为回溯进阶的过渡。“AC标准”怎么定义对我来说不是提交通过就完了。当你第一次AC之后至少再回头做三件事第一把代码里的变量名改清楚确保不看答案也能自己写出来第二算清楚时间复杂度和空间复杂度写进你的笔记里第三再提交一次看看能不能写出更短更清晰的版本。很多人在这个章节只会截图“通过”这是远远不够的。刷题的核心是训练“把复杂问题拆成模板”的能力而不是训练提交通过率。4.4 调试技巧没有print回溯题很难debug回溯题的调试天然比普通题难因为你看到的“中间结果”可能很多。但有一个很简单有效的方法在递归函数入口打印当前状态和路径用缩进表示递归深度。这样做能直观看到程序是怎么一层层尝试、回退的。print( * depth frow{row}, path{path})如果结果集不对我会先打印“每一层递归结束时的路径”检查哪一步没有撤销。如果代码超时我可以打印“剪枝前搜索的次数”看看循环到底跑了几层。实际刷题过程中依赖单步调试器不如print高效因为回溯的递归栈很深在调试器里跳来跳去容易迷路。另外一个小技巧把“选择列表”也打印出来。比如N皇后中打印row, j, dia1, dia2四个状态值能很快定位是哪个标记数组没有复位。5. 算法“回溯”和程序“栈回溯”别搞混一个调试层面的冷知识5.1 算法里的backtracking到底是什么刚接触这个领域的人很容易被“回溯”这个词误导。刷题时说的回溯英文是backtracking指的是“递归搜索 状态回退”这种算法策略。它在代码里的表现是尝试一条路失败则返回再尝试另一条路。前面所有模板都属于这类。力扣上很多题目标签都带“回溯”比如组合总和、全排列、N皇后、解数独。这些题不会涉及程序运行时栈的细节你不需要知道当前递归函数在内存地址上怎么排列只需要关心逻辑层面的选择与撤销。5.2 崩溃现场用的backtrace栈回溯gdb bt与ARM调用栈但如果你去搜“backtrace栈回溯”看到的很可能是一堆关于程序崩溃调试的内容比如gdb里执行bt命令会打印出从当前崩溃点到程序入口的函数调用序列这叫“调用栈回溯”stack backtrace。在ARM嵌入式开发里当系统发生异常时也需要通过保存的寄存器现场来回溯函数调用链定位异常发生在哪个函数。这个“栈回溯”和刷题里的“回溯算法”完全是两个概念。一个是程序运行时的行为一个是算法思想。不过两者共享同一个朴素的直觉沿着调用/选择的链条往回走找到问题出在哪一环。我遇到过不少初学者搜回溯题的时候被“栈回溯”相关文章干扰以为要去学汇编和栈帧然后被劝退。这里专门辟个谣刷题阶段你只需要把backtracking理解成“递归穷举状态重置”和运行时栈没有直接关系。当然如果你以后搞嵌入式或高性能后端学习ARM调用栈回溯和gdb的栈回溯会非常有用。它跟你做的每一道回溯算法题一样都在训练一种能力顺着调用关系找到最初的错误选择。6. 回溯题高频踩坑与排查技巧实录6.1 忘记撤销结果看似对一深看就乱这是回溯题第一大坑。最常见的症状就是第一层递归选的元素没有真正移除导致后面所有分支都带着这个“幽灵选择”。比如组合题里你写了path.append、递归调用却忘了path.pop结果就是同一个组合出现在好多不同的位置。排查方法很简单在递归返回处打印path看返回前后是否一致。如果递归前是[1,2]递归后变成[1,2,3]说明3没有撤掉那下一轮循环就会在这个污染基础上继续选。6.2 剪枝条件写反完美错过所有正确结果有段时间我写组合总和想着“如果当前sum已经超过target就return”结果把判断条件写成了if sum target: continue导致一条分支直接跳过而不是整层终止。最后结果集少了很多答案但代码不报错很难发现。排查方法是构造一个很小的测试用例比如candidates[2], target3手动模拟几层递归看程序的行为是否符合预期。小用例能很快暴露出剪枝条件的逻辑问题。6.3 递归参数设计错误list传引用导致互相影响Python里列表是可变对象如果你直接把一个列表作为参数传给递归函数然后在函数里append/pop那么所有递归层共享同一个列表。这本身没问题前提是你正确做了pop。但如果你不小心把当前列表通过path [新元素]创建一个新列表传给下一层而外部又保留了旧列表引用就可能在记录结果时把同一个列表存多次最后所有结果都变成最后一次的状态。解决办法凡是记录结果到res里一定用拷贝比如res.append(path[:])或res.append(path.copy())。这排除了绝大多数“结果集内容全部相同”的诡异bug。6.4 性能误区回溯题是不是一定要靠记忆化很多回溯题其实不需要记忆化因为剪枝已经足够。但也有一些题可以引入“记忆化”来加速比如有些带重复子问题的DFS搜索题可以把某个状态的结果缓存起来避免重复计算。N皇后、组合总和这类经典题基本不需要因为状态空间本身不大。如果超时先别急着上记忆化先检查剪枝是否没写全。剪枝到位暴力也能很快。6.5 常见问题速查表错误现象可能原因解决建议结果重复同一层去重条件写错排序后使用i startIndex and nums[i] nums[i - 1]结果缺少边界情况终止条件判断错误用最小用例模拟比如空数组、长度为1结果全变成最后一次状态记录结果时没有拷贝res.append(path[:])递归错乱/栈溢出选择列表没限制/递归深度过深检查startIndex是否更新或改用迭代显式栈代码超时剪枝不足打印搜索次数定位无效分支棋盘标记残留忘记复位visited/col数组递归返回后立即恢复标记这条表我每次刷完回溯专题都会更新一次。后面做图论题时很多DFS的bug和这里的症状一模一样排查思路完全可以复用。最后一点个人体会刷完代码随想录回溯篇四之后我最大的感受是回溯题真的没有想象中那么“玄”。它就是一个带撤销操作的DFS模板是死的难点全在“怎么选择状态”和“怎么撤销状态”。如果你现在卡在N皇后或解数独不用慌拿一张纸画出递归树把每一个状态变化写下来代码自然就清楚了。我个人还有一个习惯每做完一道回溯题就打开提交记录把通过时间最短的那版代码和我的代码做对比。这样能学到别人在剪枝上的精妙处理比自己闷头刷题效率高得多。希望这篇内容对你正在进行的刷题计划有帮助。
回溯算法进阶：N皇后、解数独等经典题型的模板与状态重置
刚把代码随想录回溯篇刷到第四篇说实话这个节点才是真正开始豁然开朗的地方。前几篇你还在跟组合、分割字符串较劲到了这一篇题目突然变成N皇后、解数独、复原IP地址、单词搜索这些“看起来就头大”的经典题。但它们本质上仍然是同一个东西递归穷举 状态重置 剪枝。这篇就结合我自己的刷题过程把回溯篇四涉及的题型、模板、易错点、调试方法都拆开聊一遍顺便回答一个很多人问过的问题算法回溯和程序崩溃时的栈回溯到底是不是一回事。如果你是正在按代码随想录刷题的人或者刚把回溯基础部分看完、想进阶到棋盘类和字符串类回溯题又或者单纯想搞明白回溯算法怎么写才不出 bug这篇文章都值得你花十分钟读完。只是建议你手上备好编辑器看到代码就自己敲一遍刷题这件事光看是不顶用的。1. 回溯篇四到底在讲什么从组合问题进阶到棋盘与穷举1.1 回溯算法能解决哪几类问题先建立一个整体图谱我刷题这么久发现回溯算法最喜欢“考试”的场景就四类组合、排列、子集、分割再加上一个棋盘/网格搜索。代码随想录回溯篇的安排也是按这个顺序走的前几篇解决组合总和、全排列、子集、分割回文串到了第四篇基本就是棋盘问题和字符串穷举问题的天下了。这样说可能会让新手有点懵我先把回溯题的类型地图画出来题型代表题核心特征组合类组合总和、组合总和II、电话号码字母组合顺序无关通常需要startIndex控制下一次搜索起点排列类全排列、全排列II顺序有关每一层都要从头开始选需要用used数组标记已选子集类子集、子集II、递增子序列收集所有节点而不是只收集叶子每次递归前都记录结果分割类分割回文串、复原IP地址对字符串进行切片需要处理子串合法性棋盘类N皇后、解数独二维递归一层递归管一行/一格状态往往是一个棋盘图/网格类单词搜索、岛屿问题DFS在网格中移动用标记数组防止走回头路回溯篇四基本就是最后三类的集中轰炸。这类题有个共同特点直接暴力循环写不干净你必须让程序有“尝试错误、回退再试”的能力。如果不提前把模板和状态重置想明白很容易写出“运行结果莫名多出很多重复结果”或者“剪枝一多就漏解”的代码。1.2 为什么搞懂回溯之后其他算法题也会变简单很多人觉得回溯就是背模板其实不是。回溯和二叉树遍历、图论DFS、动态规划、甚至是程序调试里的栈回溯底层都是同一套思维递归地进入某个状态判断这个状态行不行不行就退回上一个状态重新选。举个很直观的例子你在一个没有标记的森林里找宝藏走一条路发现是死胡同你会退回到上一个岔路口换另一条路。这个“退回上一步”的动作就是回溯。算法题里的回溯不过是把这个动作写成代码递归调用前修改状态递归返回后撤销修改。你代码里那几行path.pop()就是在模拟“从死胡同退回到岔路口”。所以我一直觉得刷回溯题最大的收获不是会做几道题而是真正理解了递归是怎么一层层展开、又一层层收回的。有了这个感觉再看深度优先遍历、动态规划的状态转移、甚至复杂的搜索题都会顺畅很多。2. 回溯的“万能模板”与状态重置原理2.1 一个模板打天下递归四要素代码随想录里的回溯模板我默写了不下二十遍最后发现模板可以浓缩成四句话确定递归函数参数、确定终止条件、遍历本层所有选择、撤销选择。用Python写基本形态是这样的def backtrack(路径, 选择列表): if 满足终止条件: 记录答案 return for 选择 in 选择列表: 做选择 # 修改路径和状态比如 path.append(x), used[i] True backtrack(路径, 新的选择列表) 撤销选择 # path.pop(), used[i] False这里最关键的其实是“撤销选择”。很多人第一遍刷题时都会犯同一个错递归进去能走到正确答案但返回上一层时忘记把状态改回去结果整个路径越走越奇怪。你只有理解了“递归返回后必须恢复现场”才算真正理解回溯。还有个细节需要提醒终止条件要写得够具体。比如求子集时庆祝“每一层递归进入时都记录当前路径”而求排列时则是在len(path) len(nums)时记录。终止条件写错通常会多出很多空结果或者重复结果。2.2 状态重置为什么有的代码要pop有的不用pop初学者最容易困惑的一个点是为什么组合题的代码里有startIndex但不用used数组排列题却必须用used数组组合和排列的本质区别就是“顺序是否重要”。组合要避免选到重复组合所以每一层递归都从startIndex开始保证下一次选的元素都排在当前元素后面例如for i in range(startIndex, len(candidates)): path.append(candidates[i]) backtrack(i 1, path, ...) # 不回头 path.pop()排列则不同[1,2]和[2,1]是两个结果。因此每一层递归都必须从头把数组扫一遍但已经用过的元素不能再用于是需要used[i]来标记for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) backtrack(path, used) path.pop() used[i] False这里需要特别注意的是只要是修改了外部状态就一定要在递归返回后恢复。比如棋盘类题目里把某个格子从.改成Q递归之后一定要再改回.。如果你用的是“局部拷贝”而不是“修改再恢复”那也可以但效率会差很多。比如path [nums[i]]这种写法每次递归都会创建新列表虽然写起来简单但大数组时会有大量内存分配。刷题时为了性能我还是更推荐在同一个列表里append/pop配合状态数组完成重置。2.3 剪枝的艺术从超时到AC往往就差一行判断回溯算法最被人诟病的就是暴力穷举指数复杂度。但加了剪枝之后很多题完全跑得动。剪枝不是玄学本质就是把已经不可能产生正确结果的分支提前砍掉。拿“组合总和II”举例如果数组里有重复数字而且每个数字只能用一次题目要求结果不能有重复组合。这里有两个剪枝层排序后如果candidates[i] ...已经超过目标值可以提前break。同一层递归中如果当前元素和前一个元素相同且前一个元素在当前层已经处理过就跳过当前元素。第二种“树层去重”是很多人的噩梦。举个例子数组是[1,1,2,4]目标值是5。第一层选了第一个1第二层再选第二个1最后组合是[1,4]但如果第一层直接选第二个1第二层就没有别的前面元素可以配合了照样会生成[1,4]从而重复。要避免这种重复常见做法是排序后判断i startIndex and candidates[i] candidates[i-1]时直接continue。这里必须用i startIndex而不是i 0因为同一路径上不同层的重复元素是允许的只有同一层内不能重复选。我自己的经验是遇到去重先画一棵递归树标出哪些节点属于同一层哪些属于不同层。树画清楚了代码就写对了。这就是代码随想录里反复强调的“树层去重”和“树枝去重”。3. 回溯篇四的经典题目实战拆解N皇后、解数独、复原IP地址、单词搜索3.1 N皇后用三个数组做列和对角线去重N皇后是回溯篇四里地位极高的一道题。问题很简单在N行N列的棋盘上摆N个皇后让它们彼此不能攻击即任意两个皇后不能在同一行、同一列、同一条对角线。代码实现思路一行一行放皇后用一个row参数记录当前处理到第几行然后遍历当前行的每一列检查该列是否安全。安全性检查可以写成函数也可以优化成三个布尔数组col[j]表示第j列是否已经被占用dia1[row j]表示从左下到右上的那组对角线是否被占用行和列之和是定值dia2[row - j n - 1]表示从左上到右下的那组对角线是否被占用行和列之差是定值加偏移避免负数。Python参考代码def solveNQueens(n): res [] board [[.] * n for _ in range(n)] col [False] * n dia1 [False] * (2 * n - 1) dia2 [False] * (2 * n - 1) def backtrack(row): if row n: res.append([.join(r) for r in board]) return for j in range(n): if col[j] or dia1[row j] or dia2[row - j n - 1]: continue board[row][j] Q col[j] dia1[row j] dia2[row - j n - 1] True backtrack(row 1) board[row][j] . col[j] dia1[row j] dia2[row - j n - 1] False backtrack(0) return res这里最有意思的点是“为什么用行和列相加/相减来代表斜线”左下到右上的斜线上所有格子的行列是同一个值左上到右下的斜线上所有格子的行-列是同一个值。所以不需要每次去检查整个对角线有没有皇后一个数组就能搞定。N皇后几乎是测试你是否真正理解状态重置的试金石因为每次递归返回都要把棋盘和三个标记数组全部复位少一行都会出诡异结果。3.2 解数独二维递归中的暴力美学解数独是回溯篇四另一座大山。它的特殊性在于递归不是一个一个处理一维数组元素而是要在9x9的棋盘上找到空位逐个尝试1到9。这就涉及“二维递归”的写法。常规思路是这样的外层函数找到一个空格内层循环尝试把1到9填进去填下之前检查是否满足行、列、九宫格约束如果满足就递归继续填下一个空格如果后续递归失败就撤销当前填入的数字继续尝试下一个数字如果9个数字都试完还是不行就返回False让上一层重新选择。这里返回True/False的写法往往比void型更好用因为你一旦找到一种可行解就可以立即层层返回不需要继续穷举。参考代码片段def solveSudoku(board): def valid(r, c, ch): for i in range(9): if board[r][i] ch: return False if board[i][c] ch: return False if board[3 * (r // 3) i // 3][3 * (c // 3) i % 3] ch: return False return True def dfs(): for i in range(9): for j in range(9): if board[i][j] .: for ch in 123456789: if valid(i, j, ch): board[i][j] ch if dfs(): return True board[i][j] . return False # 9个数字都不行 return True # 没有空格了 dfs()你会发现写完解数独之后N皇后突然变得很简单因为N皇后只是每一行选一个位置而数独每个空位都有9种可能。但它们的核心结构完全一致尝试、递归、撤销。有几个容易写错的细节九宫格下标3 * (r // 3) i // 3和3 * (c // 3) i % 3很多人第一次写不出来。推导逻辑是先根据当前行r定位到所在宫格的第一行3 * (r // 3)然后加上i // 3得到宫格内第几行列同理。实在记不住就自己画一个9宫格坐标图对照着写。3.3 复原IP地址字符串切割回溯的边界问题复原IP地址和分割回文串是同一类题但IP地址的合法性判定要求更严格地址由四段组成每段在0到255之间而且不能有前导零比如01.2.3.4不合法。切割的时候用startIndex表示当前处理到字符串的哪个位置用dotCount记录已经加了多少个点。很多人的第一版代码会写成先取出一个子串判断合法然后加一个点递归最后再删掉点。这没问题但有一个陷阱s[start:i1]如果长度大于3肯定不合法直接break如果等于0可以单独存在但00、01都不行。同时终止条件不是简单字符串用完就行而是“已经切成四段且字符串用完”。所以更清晰的状态记录方式是用一个path列表保存每一段的字符串最后再..join(path)。参考思路def restoreIpAddresses(s): res [] def backtrack(start, path): if len(path) 4: if start len(s): res.append(..join(path)) return if start len(s): return if s[start] 0: # 只能单独成一个段 backtrack(start 1, path [0]) return for end in range(start, min(start 3, len(s))): seg s[start:end 1] if int(seg) 255: continue backtrack(end 1, path [seg]) backtrack(0, []) return res这里我用的是path [seg]而不是append/pop因为字符串分段问题用不可变路径写法反而更少出错。这也印证了前面说的状态重置不是非得手动pop只要你保证传入下一层的路径是“新状态”不污染外部变量一样是正确的回溯。只是在性能要求高的时候同样建议改写为append/pop。3.4 单词搜索棋盘上的DFS与状态重置单词搜索Word Search虽然不常在回溯篇正篇里出现但我刷第四篇时经常和N皇后一起练因为它完美体现了“网格搜索状态重置”给你一个字母矩阵判断一个单词是否存在于相邻格子的连续路径中。核心逻辑是从每个格子出发如果首字母匹配就向上下左右四个方向搜索下一个字符走过的格子要标记为已访问搜索完要恢复标记。def exist(board, word): m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] def dfs(i, j, k): if k len(word): return True if not (0 i m and 0 j n): return False if visited[i][j] or board[i][j] ! word[k]: return False visited[i][j] True for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)): if dfs(i di, j dj, k 1): return True visited[i][j] False return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这里最容易错的是visited标记的位置。如果你在进入递归后没有立刻标记而是先判断条件再标记那么同一个格子可能被当前路径重复访问。另外剪枝技巧还有基于前缀的优化如果当前剩余字符长度已经大于剩余可走格子数可以提前返回但这道题一般不会卡那么狠。刷到这里你会发现棋盘类回溯题跟前面组合类最大的区别是组合题的“选择列表”是一个数字列表棋盘题的“选择列表”是坐标。一旦你能熟练把“坐标上的选择与撤销”写顺网格搜索和N皇后就都不难了。4. 刷题环境与工具链如何高效完成oj刷题和python题库刷题训练4.1 语言选择与刷题习惯我用Python刷题的理由现在很多刷题网站都支持Python。我自己的主力语言也是Python原因很直接写回溯题时Python的列表推导、切片、.join()这类操作能让逻辑非常清晰。比如恢复IP地址里..join(path)一行搞定字符串拼装用C就要多写好几行。当然不是说C/Java不好。如果你目标公司面试以C为主我建议你至少用C把每个题过一遍因为面试官可能会要求你用指定语言写。Python刷题的好处是“快速验证思路”坏处是手写细节容易被语言特性掩盖。我的习惯是平时用Python刷面试前两周把高频题每道都用Java或C再写一遍。刷题网站的选择也比较透明力扣就是最常用的题型全、讨论区质量高牛客网适合笔试模拟Codeforces、AtCoder适合打竞赛。对于跟着代码随想录刷的人来说力扣足够因为代码随想录里的题号基本都对应力扣原题。4.2 从代码随想录到labuladong刷题笔记怎么搭配使用很多人在评论区问代码随想录和labuladong的刷题笔记到底选哪个我的看法是两者不冲突。代码随想录的好处是“刷题路线固定”每一章告诉你先做哪些题再做哪些题特别适合不知道怎么安排顺序的人。labuladong则更侧重“算法框架”比如他反复强调的回溯算法是“多叉树的遍历”和代码随想录里的模板其实殊途同归。我自己使用的策略是主线按代码随想录的题目顺序刷卡壳的时候去看labuladong对同一类题的框架总结。比如我刷N皇后之前就在labuladong的笔记里看到一句话回溯算法就是“路径 选择列表 结束条件”。这句话和代码随想录的模板互相印证双倍加深记忆。但是我不建议两种资料同时从头通读否则你会陷入“今天看这个明天看那个”的混乱。更好的做法是选一套作为主线另一套作为参考字典。看到某个知识点不懂再打开另一套书签找到对应章节。4.3 力扣刷题攻略题号顺序、难度控制和AC标准代码随想录回溯篇四的题号区间大致集中在37、51、52、79、93、131、332这类题号上。我建议按“从易到难”重新排序刷先做复原IP地址93、分割回文串131再做N皇后51、解数独37最后再做重新安排行程332和单词搜索79。因为前两个纯粹是字符串切分不涉及二维坐标的抽象适合作为回溯进阶的过渡。“AC标准”怎么定义对我来说不是提交通过就完了。当你第一次AC之后至少再回头做三件事第一把代码里的变量名改清楚确保不看答案也能自己写出来第二算清楚时间复杂度和空间复杂度写进你的笔记里第三再提交一次看看能不能写出更短更清晰的版本。很多人在这个章节只会截图“通过”这是远远不够的。刷题的核心是训练“把复杂问题拆成模板”的能力而不是训练提交通过率。4.4 调试技巧没有print回溯题很难debug回溯题的调试天然比普通题难因为你看到的“中间结果”可能很多。但有一个很简单有效的方法在递归函数入口打印当前状态和路径用缩进表示递归深度。这样做能直观看到程序是怎么一层层尝试、回退的。print( * depth frow{row}, path{path})如果结果集不对我会先打印“每一层递归结束时的路径”检查哪一步没有撤销。如果代码超时我可以打印“剪枝前搜索的次数”看看循环到底跑了几层。实际刷题过程中依赖单步调试器不如print高效因为回溯的递归栈很深在调试器里跳来跳去容易迷路。另外一个小技巧把“选择列表”也打印出来。比如N皇后中打印row, j, dia1, dia2四个状态值能很快定位是哪个标记数组没有复位。5. 算法“回溯”和程序“栈回溯”别搞混一个调试层面的冷知识5.1 算法里的backtracking到底是什么刚接触这个领域的人很容易被“回溯”这个词误导。刷题时说的回溯英文是backtracking指的是“递归搜索 状态回退”这种算法策略。它在代码里的表现是尝试一条路失败则返回再尝试另一条路。前面所有模板都属于这类。力扣上很多题目标签都带“回溯”比如组合总和、全排列、N皇后、解数独。这些题不会涉及程序运行时栈的细节你不需要知道当前递归函数在内存地址上怎么排列只需要关心逻辑层面的选择与撤销。5.2 崩溃现场用的backtrace栈回溯gdb bt与ARM调用栈但如果你去搜“backtrace栈回溯”看到的很可能是一堆关于程序崩溃调试的内容比如gdb里执行bt命令会打印出从当前崩溃点到程序入口的函数调用序列这叫“调用栈回溯”stack backtrace。在ARM嵌入式开发里当系统发生异常时也需要通过保存的寄存器现场来回溯函数调用链定位异常发生在哪个函数。这个“栈回溯”和刷题里的“回溯算法”完全是两个概念。一个是程序运行时的行为一个是算法思想。不过两者共享同一个朴素的直觉沿着调用/选择的链条往回走找到问题出在哪一环。我遇到过不少初学者搜回溯题的时候被“栈回溯”相关文章干扰以为要去学汇编和栈帧然后被劝退。这里专门辟个谣刷题阶段你只需要把backtracking理解成“递归穷举状态重置”和运行时栈没有直接关系。当然如果你以后搞嵌入式或高性能后端学习ARM调用栈回溯和gdb的栈回溯会非常有用。它跟你做的每一道回溯算法题一样都在训练一种能力顺着调用关系找到最初的错误选择。6. 回溯题高频踩坑与排查技巧实录6.1 忘记撤销结果看似对一深看就乱这是回溯题第一大坑。最常见的症状就是第一层递归选的元素没有真正移除导致后面所有分支都带着这个“幽灵选择”。比如组合题里你写了path.append、递归调用却忘了path.pop结果就是同一个组合出现在好多不同的位置。排查方法很简单在递归返回处打印path看返回前后是否一致。如果递归前是[1,2]递归后变成[1,2,3]说明3没有撤掉那下一轮循环就会在这个污染基础上继续选。6.2 剪枝条件写反完美错过所有正确结果有段时间我写组合总和想着“如果当前sum已经超过target就return”结果把判断条件写成了if sum target: continue导致一条分支直接跳过而不是整层终止。最后结果集少了很多答案但代码不报错很难发现。排查方法是构造一个很小的测试用例比如candidates[2], target3手动模拟几层递归看程序的行为是否符合预期。小用例能很快暴露出剪枝条件的逻辑问题。6.3 递归参数设计错误list传引用导致互相影响Python里列表是可变对象如果你直接把一个列表作为参数传给递归函数然后在函数里append/pop那么所有递归层共享同一个列表。这本身没问题前提是你正确做了pop。但如果你不小心把当前列表通过path [新元素]创建一个新列表传给下一层而外部又保留了旧列表引用就可能在记录结果时把同一个列表存多次最后所有结果都变成最后一次的状态。解决办法凡是记录结果到res里一定用拷贝比如res.append(path[:])或res.append(path.copy())。这排除了绝大多数“结果集内容全部相同”的诡异bug。6.4 性能误区回溯题是不是一定要靠记忆化很多回溯题其实不需要记忆化因为剪枝已经足够。但也有一些题可以引入“记忆化”来加速比如有些带重复子问题的DFS搜索题可以把某个状态的结果缓存起来避免重复计算。N皇后、组合总和这类经典题基本不需要因为状态空间本身不大。如果超时先别急着上记忆化先检查剪枝是否没写全。剪枝到位暴力也能很快。6.5 常见问题速查表错误现象可能原因解决建议结果重复同一层去重条件写错排序后使用i startIndex and nums[i] nums[i - 1]结果缺少边界情况终止条件判断错误用最小用例模拟比如空数组、长度为1结果全变成最后一次状态记录结果时没有拷贝res.append(path[:])递归错乱/栈溢出选择列表没限制/递归深度过深检查startIndex是否更新或改用迭代显式栈代码超时剪枝不足打印搜索次数定位无效分支棋盘标记残留忘记复位visited/col数组递归返回后立即恢复标记这条表我每次刷完回溯专题都会更新一次。后面做图论题时很多DFS的bug和这里的症状一模一样排查思路完全可以复用。最后一点个人体会刷完代码随想录回溯篇四之后我最大的感受是回溯题真的没有想象中那么“玄”。它就是一个带撤销操作的DFS模板是死的难点全在“怎么选择状态”和“怎么撤销状态”。如果你现在卡在N皇后或解数独不用慌拿一张纸画出递归树把每一个状态变化写下来代码自然就清楚了。我个人还有一个习惯每做完一道回溯题就打开提交记录把通过时间最短的那版代码和我的代码做对比。这样能学到别人在剪枝上的精妙处理比自己闷头刷题效率高得多。希望这篇内容对你正在进行的刷题计划有帮助。
