真正把回溯算法搞明白不是在背模板那一刻而是当你意识到它本质是在一棵决策树上走到底、退回来、再换一条路的时候。我当初学到这里卡了很久递归单独看能懂一到撤销选择就开始怀疑状态到底去哪了。这篇文章就按我自己趟出来的理解路径写把回溯算法的本质、通用模板、几个经典题的变形、剪枝思路和常踩的坑一次讲透。如果你是准备算法面试或者在项目里需要做枚举型搜索沿着这套思路往下走大部分回溯场景都能直接套用。1. 回溯算法到底在解哪类题1.1 本质在一棵决策树上做深度优先搜索理解回溯最省力的方式是把它看成在决策树上做深度优先搜索。想象你站在分岔路口每个路口都有好几条路任务是找出所有能从起点到终点的走法。最直接的办法是挑一条路走到头发现不对就退回路口换一条。这个退回来继续试的动作就是回溯名字的由来。严格一点讲回溯就是递归遍历一棵隐式的决策树树的每个节点代表一个中间状态每条边代表一次选择叶子节点代表完整结果。所谓深度优先是指先把一条分支走到不能再走再回到上一个分支点换方向。这也是为什么回溯和递归几乎绑定出现——递归天然适合表达进入子问题再返回父问题的过程而回溯只是在递归返回之后多做了一步恢复现场。全排列是最直观的例子。给定 [1,2,3]你先固定第一位是 1剩下的 [2,3] 继续选第一位是 1 的所有排列枚举完再把第一位改成 2从头来过。这个固定一个数字递归处理剩余数字的过程就是在一棵以空排列为根、以每个可放数字为边的多叉树上做深度优先搜索。1.2 和暴力枚举的差别在剪枝两个字很多人问回溯不就是暴力枚举吗答案有对有错。它确实是暴力枚举但它是带剪枝的暴力枚举。普通暴力枚举会把所有组合都生成出来再统一判断合法性回溯则每走一步就先判断这条分支还有没有可能成为合法解没有就直接砍掉。举个例子。求 [1,2,3] 的全排列时用 used 数组标记数字是否被用过这一步就已经在剪枝如果第一位选了 1那所有把 1 放在后面的分支根本不会被遍历到。这就是可行性剪枝也是回溯比纯嵌套循环枚举省时间的原因。另外暴力枚举用嵌套循环实现时循环层数必须在一开始就知道回溯通过递归天然支持层数可变可以处理 n 不固定的场景。比如 n 皇后棋盘大小由参数决定不可能为每一种大小写一套固定层数的循环。1.3 三个信号帮你识别回溯题做题多了我总结出三个信号只要同时满足基本可以往回溯方向想题目要求找出所有……而不是找出最优解。解可以逐步构造每一步的选择会影响后续选择。中间状态存在可提前判断的合法性约束。典型题目包括全排列、组合、子集、括号生成、分割回文串、N皇后、数独、图着色。反过来如果题目是求最优化且存在重叠子问题先考虑动态规划如果能局部决策且无后效性贪心更合适。这个判断本身也是面试中考察算法设计能力的重要环节。2. 回溯模板拆解路径、选择列表、结束条件2.1 路径、选择列表、结束条件三要素缺一不可回溯框架可以压缩成三件事路径、选择列表、结束条件。路径已经做过的选择也就是从根节点到当前节点的状态。选择列表当前这一步还能选哪些内容。结束条件什么时候这条路径可以记录成最终答案。拿全排列来说路径是 path 数组里已经排好的数字选择列表是还没被使用的数字结束条件是 path 长度等于 nums 长度。拿子集来说路径是当前已经选入的元素选择列表是从哪个位置之后还能继续选结束条件和全排列不同——子集的每个节点都可以作为结果记录不需要等到叶子。把三要素想清楚模板基本就能背下来。很多人写不出来不是因为语法问题而是因为这三个东西没在动笔前定义好。2.2 一套能直接落地的通用模板用 Python 写最通用的模板长这样result [] def backtrack(path, choices): if 满足结束条件: result.append(path[:]) # 保存一份快照 return for choice in choices: if 该选择不合法: continue # 剪枝 path.append(choice) # 做选择 backtrack(path, 新的选择列表) # 递归 path.pop() # 撤销选择 backtrack([], 初始选择列表) return result这里我特意把做选择、递归、撤销三行写在一起。实际题目中选择列表往往不是显式传进去而是通过 used 数组、start 索引或位掩码来维护。但框架骨架不变。注意result.append(path[:])这一行它存的是 path 的一份拷贝而不是 path 本身。原因在后面的坑位部分会详细说先记住这个习惯。2.3 为什么每次递归完都要撤销这一步是新手最懵的地方。关键在于递归全程共享的是同一个 path 列表对象而不是副本。假设递归返回后不撤销第一个分支留下的元素会被第二个分支继续背着第二个分支一开始就不是从空状态出发而是从污染过的历史状态出发结果势必全错。如果你问那我在递归时传一个新列表进去不就可以不撤销吗确实可以但代价是每一层都创建新数组空间开销和拷贝成本都高代码可读性也差。标准写法都是在同一份状态上做选择—递归—撤销保证返回上层时状态绝对干净。这个原则和带状态指针的 DFS 遍历完全一致理解了它回溯就算通了。3. 从全排列到N皇后三道题吃透模板变形3.1 全排列模板最小可运行版本先看最朴素的全排列。给定不重复的 nums返回所有全排列。代码几乎是照着模板抄的path 记录已选数字used 数组记录哪些位置已用结束条件是 path 长度等于 n。def permute(nums): res, path [], [] n len(nums) used [False] * n def dfs(): if len(path) n: res.append(path[:]) return for i in range(n): if used[i]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res执行时dfs 先固定第一位为 nums[0]一路递归到收集完所有以它开头的排列再一层层退回。每退一层就恢复 used 和 path。这就像深度优先遍历完一棵子树后把该子树占用的状态还给父节点。复杂度上排列树第一层有 n 个节点第二层 n(n-1) 个总节点数是 n! 级别每个叶子还要拷贝一次结果做快照成本 O(n)所以整体时间复杂度 O(n·n!)。递归深度是 n空间 O(n)。3.2 组合和子集start 参数是怎么被逼出来的组合题和全排列有个关键区别顺序不重要。组合里 [1,2] 和 [2,1] 是同一个结果。如果照搬全排列模板会把这两个都生成出来产生大量重复。解决办法是引入 start 参数强制每一步只能从 start 之后的元素中选。这样生成出来的下标序列一定是递增的从机制上杜绝了重复。以组合 C(n, k) 为例def combine(n, k): res, path [], [] def dfs(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1) path.pop() dfs(1) return res这里dfs(i 1)保证了下一步只能选比当前更大的数字所以 [1,2] 会出现[2,1] 根本不会被构造。子集题更简单只需要把结束条件改掉每进入一层不管 path 多长都先把当前 path 存进 res再继续扩展。这也是子集题代码很短但出现频率很高的原因。记住一个规律组合、子集类问题模板里一定离不开 start它的含义是搜索方向单向不回看。3.3 N皇后把合法检查前置到放子之前N皇后是回溯里约束最多的经典题。要求把 n 个皇后放在 n×n 棋盘上互相不能同行、同列、同对角线。按行向下放每放一个皇后前先检查目标列和对角线是否安全安全才放。这个检查动作本身就是剪枝而且发生在递归入口之前。def solve_n_queens(n): res [] cols [-1] * n # cols[row] 表示第 row 行皇后所在的列 def is_safe(row, col): for r in range(row): c cols[r] if c col or abs(c - col) abs(r - row): return False return True def dfs(row): if row n: res.append([.join(Q if cols[i] j else . for j in range(n)) for i in range(n)]) return for col in range(n): if is_safe(row, col): cols[row] col dfs(row 1) cols[row] -1 dfs(0) return res对角线的判断是abs(c - col) abs(r - row)意思就是两个皇后的行差等于列差说明它们在一条斜线上。因为我们是按行放同一行的冲突天然不存在所以只需要检查列和对角线。这道题最能体现搜索 剪枝的组合拳is_safe 每检查一次就砍掉一整棵子树。从全排列到组合再到N皇后你会发现模板没有变化变的只是三要素的具体定义和剪枝条件。4. 剪枝不是可选优化它决定回溯能不能用4.1 两类最容易见效的剪枝回溯天然是暴力的真正让它能在现实数据下跑完的是剪枝。我把最常用的剪枝分成两类。第一类是可行性剪枝当前节点已经不满足约束直接不进入递归。全排列里 used 数组跳过已用数字、N皇后里 is_safe 检查都属于这一类。第二类是上下界剪枝当前这一步继续走下去也不可能得到合法解或更优解直接跳过。最典型的例子是组合总和问题先把 candidates 排序在循环中如果当前和 candidates[i] target由于后面的元素更大全都不可行可以直接break。这个 break 比 continue 更狠因为它跳过的是一整段后缀而不是单个元素。我见过不少同学把 continue 写遍全场结果剪枝效果聊胜于无。排序预处理往往能带来数量级的差别。4.2 重复元素去重剪的是同一层而不是同一条路径输入里若带重复元素比如 [1,1,2]求全排列或组合时会出现重复结果。核心原则一句话同一层递归中相同值只尝试一次不同层允许使用相同值。组合/子集场景通常在排序后加一个判断if i start and nums[i] nums[i - 1]: continue全排列场景因为有 used 数组写法略有不同if used[i]: continue if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue第二种写法里的not used[i - 1]是对新手最绕的一点。它保证的是只有当上一个相同元素已经作为同等地位的选择被跳过后当前元素才跳过。如果 used[i-1] 为 True说明前一个相同值已经在当前路径里使用那当前这个相同值就属于在不同层使用相同值是合法的。理解了这个再去写子集 II组合总和 II就会发现所有带重复元素的题目最终都落在这一个判断上。4.3 位运算剪枝性能党的加分项状态量不大但搜索很深的题可以用整数的位来表示集合。子集枚举就是个典型n 个元素的所有子集可以直接遍历 0 到 2^n-1每个数字的二进制位代表对应元素选还是不选n 不超过 20 时非常快连递归都不用写。N皇后也可以用三组 bitmask 分别记录已占用的列、主对角线、副对角线。递归时把三个掩码按位或起来就能在 O(1) 时间内判断某个位置可不可以放。实测下来n 较大时速度优势很明显。不过位运算代码可读性差面试时如果不是明确要求性能我通常先用数组和循环把思路讲清楚再提如果想优化可以用位掩码。思路比写法重要先保证正确再谈优化。5. 回溯题里最容易被忽略的坑5.1 结果集被同一个空列表污染这是 Python 回溯题里最经典的错误res.append(path)而不是res.append(path[:])。因为列表是引用类型后续 path.pop() 会把已经存进 res 的那些答案一起改掉。最终结果集里全是同一个列表的不同引用内容变成被清空或最后残留的状态。正确写法是res.append(path[:])或list(path)花一次拷贝成本换取一份稳定快照。这个坑几乎每个人都会踩一次面试时出现观感极差写模板时刻意记住。5.2 撤销操作的位置决定状态是否干净撤销必须和做选择一一对应。常见错误有两类一是递归返回后忘了 pop状态被越堆越长二是在某个 if 分支里直接 return没走撤销逻辑把状态搞脏。我的习惯是把做选择—递归—撤销三行绑在一起任何提前 continue 或 return 都放在做选择之前。如果递归内部有异常提前返回的可能就直接在 finally 里做恢复。别嫌啰嗦真出 bug 时这种问题极难定位因为错误状态要跑很深才会爆发肉眼根本看不出来。5.3 复杂度分析阶乘、指数和递归深度回溯的复杂度一般看状态树上的节点数乘以每个节点的操作成本。以全排列为例第一层 n 个节点第二层 n(n-1)第三层 n(n-1)(n-2)总节点数是 n! 级别每层还有常数操作所以时间 O(n!)若算上结果拷贝则是 O(n·n!)。组合 C(n,k) 是组合数级别子集是 2^nN皇后近似 n! 但剪枝后实际远小于这个数。面试时养成随口说出最坏情况指数/阶乘的习惯。同时要清醒剪枝只会降低期望耗时和常数最坏复杂度并不会因此改变。正因为这样一旦输入规模超过可控范围就该考虑回溯是不是真的合适。5.4 什么时候该果断放弃回溯n 超过 20 还要枚举所有子集回溯基本不可能在 1 秒内跑完。这时先退一步想题目是不是求最优而不是全部解是不是可以排序后贪心状态能不能合并成动态规划回溯不是一个什么都能糊一层上去的万能答案。它是一个兜底方案适用条件是确认必须枚举、规模可控、剪枝充分。我见过不少人一看到所有可能就立刻套回溯结果在大数据规模下超时后才开始懊恼。正确的顺序应该是先做问题归类再决定用什么套路。再分享一个小习惯拿到回溯题第一步不是写代码而是先在草稿纸上画一棵决策树。挑一个小例子比如 n3 的全排列手动走两三个分支把每层的路径、选择列表和剪枝条件写清楚再去套模板。这样做既能提前定位剪枝点也会让你意识到哪些状态是可以合并的——真到要优化的时候你已经比别人先完成了最关键的一步。我就是靠这个笨方法从背模板过渡到能设计状态的希望你也能用上。