1. 回溯算法到底在解决什么问题写在第二十五天这个节点上我正好学完递归、二叉树和深度优先遍历开始碰回溯算法。说实话回溯这个名词听上去高大上拆开看就是“一条路走到黑走不通就退回来换条路再走”。它本质上是DFS深度优先搜索在解空间树上的应用核心是“试探 撤销”常用来解决组合、排列、子集、切割、棋盘、数独、图着色这类找不到数学通解、只能系统性枚举所有候选解的题目。回溯解决的问题有个共同特征你需要做一串决策每个决策都有若干选项而且约束条件会随着决策推进而变化。比如全排列你要依次决定第一位放哪个数、第二位放哪个数已经用过的数不能再放N皇后你要逐行决定皇后放在哪一列且不能与之前已放的皇后互相攻击。这类问题如果硬写for循环层数不固定根本不知道嵌套几层而回溯用递归把“嵌套层数不固定”这件事自然消化掉了。所以我的第一个体会是回溯不是一种新算法而是一种组织搜索过程的方式。理解了递归回溯的骨架就理解了一半理解了DFS回溯的遍历顺序就理解了另一半。剩下要练的就是“选择、撤销、剪枝”这一套动作。很多人都说回溯模板背熟就能写我不完全同意。模板只是骨架真正难的其实是判断什么算一条可行路径、什么时候该剪、什么时候需要撤销这些只有靠动手画递归树才能真的想明白。2. 回溯怎么写才不乱模板与三个关键动作我学回溯时最受益的动作是画递归树。把问题解空间画成一棵树树的每条从根到叶子的路径就是一个候选解回溯算法要做的事情就是在这棵树上做深度优先遍历用约束条件给树剪枝。画完树再写代码不靠背也不容易丢条件。几乎所有回溯题都可以套下面这个结构def backtrack(path, 状态参数): if 满足终止条件: 结果.append(path[:]) return for 分支 in 可选列表: if 分支不满足约束: continue # 剪枝 做选择 backtrack(path, 新状态) 撤销选择这里的关键动作有三个选择、剪枝、撤销。选择就是把当前分支加进部分解剪枝是在进入分支前判断它是否还有希望没希望就直接跳过撤销则是递归返回后把刚才的选择退掉恢复现场这样for循环里的下一次迭代才能拿到干净状态。我一开始常犯的错误是只记得做选择和递归忘记撤销。后果特别直观如果做选择后不撤销前面的分支会给后面的分支留下脏数据最终要么结果重复要么结果是一堆错误路径。反过来如果撤销时机不对比如撤销放在了递归之前那结果根本不会产生分支。画递归树能非常清楚地看到撤销动作发生在什么时候在当前节点的所有子分支都探索完毕之后回到当前节点时再做撤销。这里有一个很关键的小技巧递归函数里修改了共享的可变对象比如用一个列表path装当前路径返回上一层时一定要恢复原样。理解了这一点就理解了为什么树形DFS和普通DFS写法大同小异也理解了为什么回溯代码里总是成对出现append和pop。3. 全排列第一道让我真正开窍的回溯题学回溯绕不过的入门题是全排列给定一个不重复数组比如[1,2,3]返回所有可能的排列。这道题我一开始想用脑子硬想想了半天觉得排列数不就是n的阶乘吗每个排列往里填数字就行但代码就是写不出来因为不知道循环该写多深。后来按递归树的思路写很快通了每一层决定一个位置用一个used数组记录哪些数已经被选过深度达到数组长度时记录结果。def permute(nums): res [] path [] used [False] * len(nums) def dfs(): # 终止条件排完所有位置 if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) dfs() # 撤销选择 used[i] False path.pop() dfs() return res代码看起来短细节却密集。第一为什么res.append(path[:])而不是res.append(path)因为path是可变的后续递归会不断修改它如果直接append最终结果数组里存的都是同一个引用全部会变成最后一次状态。path[:]相当于快照把当前内容复制一份存进去。这个坑我踩过结果就是返回了一堆一模一样的空列表排查了很久才反应过来。第二为什么撤销顺序是used[i]False和path.pop()按我的习惯撤销要跟做选择成镜像顺序先加进去的后恢复后加进去的先恢复。这样不容易乱。如果某些人习惯先把used恢复再pop也没问题但要保证最终状态跟递归进来之前一致。第三复杂度。全排列共有n!个叶子节点加上分支路径数总复杂度是O(n * n!)级别做完单个排列拷贝一次还要O(n)所以大数量级下完全跑不动。回溯本来就不是为了高效解决规模问题它是为了在不确定性搜索空间里“不重不漏”地找答案这种“指数级”是这个问题本身的性质。4. 组合总和与剪枝回溯不是傻傻穷举全排列学会了下一个让我进阶的是组合总和系列。典型题目是给定一个无重复元素的数组candidates和一个目标数target找出candidates中所有可以使数字之和等于target的组合candidates中的数字可以无限制重复被选取。初看这道题我按全排列的套路写写出了重复答案比如[2,2,3]和[3,2,2]都被收集了。原因就是我把组合当成排列做了每个位置可以从所有数字中选自然会产生顺序不同但元素相同的组合。解决的办法就是把搜索方向固定住每一层递归传入startIndex只从当前下标往后选数字避免因为回头选而产生重复。def combination_sum(candidates, target): res [] path [] def dfs(start, remain): if remain 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remain: continue path.append(candidates[i]) dfs(i, remain - candidates[i]) path.pop() dfs(0, target) return res组合总和这题最简单版本允许元素重复使用所以递归时传入的还是i不是i1。如果题目改成每个元素只能用一次就换成i1同时还要处理重复元素去重问题比如给定数组本身有重复数字同一层for循环跳过相同值因为同一个数字在同一层选一次就够了再选会产生重复分支。“剪枝”这个词虽然听起来抽象但在组合总和里落地非常具体一种是可行性剪枝如果当前candidates[i]已经大于剩余需要的remain直接跳过因为后面数字只会更大一种是重复分支剪枝比如istart时已经选了某个值下一轮istart1还是同一个值说明同一层重复遍历相同选择直接continue。这些剪枝让搜索效率提升一个量级而且结果不变。我建议学到这里时一定要把递归树画下来尤其是看“同一层跳过相同值”为什么不会漏解。同一层是“选第几个数”这一维度同一个维度下选相同的数字得到的后续搜索空间完全相同只保留第一次就够了。5. N皇后从一维递归到二维棋盘做完组合题后我觉得自己已经会回溯了结果被N皇后劈头盖脸打回来。这道题的经典之处在于选择不再发生在数组中而发生在棋盘坐标上约束条件不是“是否用过某个数”而是“是否行列冲突、是否对角线冲突”。它让我意识到回溯的核心代码框架不变但状态抽象需要随问题场景灵活变化。N皇后要求把N个皇后放在NxN棋盘上任意两个皇后不能在同一行、同一列、同一条对角线上。常见写法是一行一行放皇后每层递归代表处理一行for循环遍历当前行可以放皇后的列用col数组记录每行皇后放在第几列放之前检查当前坐标跟之前行是否冲突。def solve_N_queens(n): res [] board [-1] * n # board[行] 列 def is_valid(row, col): for i in range(row): if board[i] col: return False if abs(board[i] - col) abs(i - row): return False return True def dfs(row): if row n: res.append([. * i Q . * (n - i - 1) for i in board]) return for col in range(n): if not is_valid(row, col): continue board[row] col dfs(row 1) board[row] -1 # 撤销 dfs(0) return res这个写法我觉得是最直观的一版。is_valid里的第i行皇后所在列是board[i]如果它跟当前列相同说明同列冲突如果两个行号之差等于两个列号之差说明两个皇后在当前棋盘的对角线上。对角线判断用abs差值这一步是N皇后最容易写错的地方我第一次只判断了主对角线漏了副对角线的情况导致输出里出现斜着攻击的皇后。N皇后还让我体会到一个事回溯撤销的本质是“程序栈保存现场”。递归调用返回后函数里局部变量都还在但共享数组需要手动恢复。所以board[row] -1这一行绝对不能省。如果不恢复本行放完再尝试下一列时前面的行数据会错乱。6. 剪枝技巧的进阶不只是“if continue”前几道题让我会写基础回溯了但一到LeetCode上某些中等困难题数据规模稍微大一点直接超时。这时候才意识到回溯题写对只是第一步剪枝才是拉开差距的地方。我总结出几个比较实用的剪枝思路。第一是可行性剪枝。在进入递归前判断是否已经不可能得到目标解。例如组合总和中if candidates[i] remain就跳过子集问题里如果当前路径长度已经超过目标直接return。这个最简单也最常用。第二是重复性剪枝。对原始数组排序让相同的数相邻然后在同一层for循环里判断if i start and nums[i] nums[i - 1]: continue。这样保证每个重复元素只在当前位置被选一次避免产生重复结果。这个我一开始学得最困惑为什么nums[i] nums[i-1]时不跳而是要i start才跳因为i start时是当前层的第一个选择必须进入而当i start时说明之前已经有过相同数值的选择当前选择是“换了个相同的数”不会产生新解。第三是排序剪枝。很多回溯题在开始搜索前先排序不仅仅是为了去重还为了利用有序性提前结束循环。比如组合总和如果数组升序一旦candidates[i]大于remain后面所有数都大于remain直接break而不是continue。这样for循环不会带着“后面还可能可行”的幻想继续空转。第四是更高级的位运算剪枝主要用于N皇后这类问题。用整数二进制位表示哪些列已被占用、哪些对角线已被占用替代数组判断冲突的时间从O(n)降到O(1)。这是空间换时间也是把状态压缩进一个整数的经典练习。但对初学者来说先写数组版本能AC之后再去优化成位运算更稳妥。还有一个概念要区分清楚回溯和动态规划都能解决“决策型”问题但回溯求的是所有可行解动态规划求的是最优值或可行性。很多题看起来都能用两种思路比如从左上角到右下角的路径问题回溯可以枚举所有路径但数据一大就超时动态规划因为存在重叠子问题可以大幅加速。所以遇到题先判断是否存在重叠子问题有的话优先考虑DP没有或要输出全部方案才用回溯。这是我学了二十多天算法后对“什么问题用什么方法”比较深的一次体会。7. 回溯常见报错与排查思路整理成我的速查表这段时间刷回溯题我踩过的坑完全可以整理成一个速查表。写出来一方面给自己以后复习用另一方面也帮初学者少走弯路。我从“症状”出发倒推原因排查起来会快很多。症状常见原因排查思路结果为空或非常少终止条件写错比如把len(path)应该等于n写成大于n打印递归入口时的path和进入条件看递归树走到哪一层就停了结果重复组合题里没有用startIndex或者同一层没有跳过重复元素画递归树检查是否出现同一层选相同值检查startIndex是否传错结果全是同一个列表用res.append(path)而不是res.append(path[:])复制一份path再入结果正确解被剪掉剪枝条件作用域理解错比如continue放在不恰当的位置把剪枝条件临时注释掉看是否能输出完整结果再逐步恢复递归深度过大或超时没有剪枝或者状态空间本来就是指数级先考虑可行性剪枝再考虑排序、记忆化确认是否该换DP撤销不完整某个分支提前return时没执行撤销代码统一用“先撤销再return”的模式或者把撤销放在递归返回后的统一位置除了表格里的内容我调试回溯代码最推荐的方式是加打印。比如在dfs开头打印当前path和传入的start或row参数在撤销后打印“撤销xx”。这样每次递归进出都能看到实体树长什么样。等确认逻辑正确再把打印删掉。还有一个小技巧是“单测小数据”。比如全排列拿[1,2]来测组合总和拿candidates[2,3,6,7], target7来测N皇后拿n4来测。小数据下结果数量少能人工验证正确性出现问题也容易定位。我见过不少同学一上来就跑大数据超时之后根本不知道是逻辑错了还是性能不够这是最浪费时间的学习方式。8. 第二十五天的真实体会回溯怎么才能真学会学到今天我对回溯最直观的感受是它不是靠背代码学会的是靠画递归树和反复debug学会的。我见过有人能把模板一字不差写出来但碰到变体题立刻懵因为他不清楚模板里每个变量的含义。比如startIndex到底什么时候传i什么时候传i1表面上是“允不允许重复使用同一个元素”的区别实质上是“是否可以回到当前分支再选自身”的区别。只有把递归树的层级结构想明白才能随机应变。对我来说今天值得记录的收获有三块。第一回溯模板本身非常稳定写题时先把终止条件、for循环、选择、递归、撤销这五件事列出来至少能保证结构完整。第二剪枝的优先级高于暴力搜索排序和去重是性价比最高的两类优化遇到规模稍大的题不要急着写裸回溯先看能不能排序能不能跳过重复分支。第三调试时把递归树打印出来比什么都强我花五分钟打印胜过半小时干瞪眼。接下来我打算再把回溯的经典题型过一遍尤其是字符串切割、子集、棋盘类问题这些都会反复用同样的思想。另外我会把回溯和动态规划放在一起对比联系因为很多题两种解法都能做对比中能加深对算法边界的理解。学算法这件事真的急不来一天一个知识点后面回头看量变慢慢就变成质变了。