企业官网建设流程全解析

回溯算法这四个字，刷过算法题的人都不陌生。它几乎是面试题里出现频率最高的那批——全排列、组合总和、N皇后、数独、括号生成，全是它的地盘。可我当年第一次看回溯代码时，满脑子只有一个疑问：递归我懂，for循环我也懂，为什么递归套for循环之后，还要写一行path.pop()？这行代码到底在干嘛？

后来我才想明白，回溯的本质就是在一棵决策树上做深度优先遍历，而那个pop，就是在从死胡同里退出来的时候，把自己留下的脚印擦掉。这篇文章我想把回溯这层窗户纸彻底捅破，用三道最经典的题带着你从头到尾走一遍：怎么画决策树、怎么写模板、怎么剪枝、怎么调试。看完你会发现，回溯真的就那三板斧，套路感极强。

1. 回溯算法的核心：为什么递归之后还要撤销操作

1.1 把回溯理解成走迷宫

先跟你聊个场景。你在一个迷宫里找出口，面前有三条岔路，你选了一条往前走。走了五十米发现是死胡同，这时候你会怎么办？肯定要退回刚才的岔路口，换另一条路继续走。

关键在于“退回”这个动作。你要是退回来了，但手上还攥着刚才那条路捡到的标记物，甚至把岔路口的路牌都改了，那再走其他路的时候就会被干扰，决策就乱了。回溯算法里那个path.pop()，干的就是“退回岔路口、把标记物放下、把路牌复原”这件事。

从计算机的角度说，递归调用就在不断往下钻，每钻一层相当于多走了一条路；当递归返回时，如果不清除当前层做出的选择，那么同一层的其他选择会被旧数据污染，最后的结果必然出错。所以说，有递归就未必有回溯，有回溯就一定有状态重置。这也是回溯和普通递归最大的区别。

很多人会把回溯和DFS（深度优先搜索）混为一谈，其实回溯是DFS的一种典型应用。DFS强调的是“一条路走到黑”的遍历方式，而回溯更强调“走不通就退回来恢复现场”的处理逻辑。凡是要你枚举所有可能组合、排列、路径的问题，基本都属于回溯的射程范围。

1.2 回溯三要素和通用代码骨架

回溯问题的解法高度统一，核心就是三个要素：路径、选择列表、结束条件。对应到代码上，是三个东西加起来组成了那个经典模板。

• 路径：已经做出的选择，也就是当前已经走到哪一步了，通常用一个path列表保存。
• 选择列表：当前状态下还能做哪些选择，通常用参数start或used数组来控制。
• 结束条件：什么时候说明一条合法路径已经完整了，可以把结果保存下来。

通用的代码骨架长这样：

def backtrack(路径, 选择列表): if 满足结束条件: 结果列表.append(路径[:]) return for 选择 in 选择列表: 做选择 # 把选择加入路径 backtrack(路径, 新的选择列表) 撤销选择 # 把选择从路径中移除

你去看任何一道回溯题，套的都是这四步。区别只在于“结束条件怎么判定”和“选择列表怎么生成”。

有一个细节必须提前说：结果列表里存的通常是path[:]，而不是path本身。因为path在递归过程中一直在变，如果直接存path，你存的是同一个列表对象的引用，等回溯结束后再去读，里面早就被清空了。用path[:]是复制一份当前快照，保存的才是当时那一条完整路径。

2. 组合总和实战：一道题吃透回溯的完整流程

2.1 题目分析和决策树怎么画

LeetCode 39题“组合总和”是我最推荐用来入门回溯的题目，没有之一。题目说，给你一个无重复元素的整数数组candidates和一个目标数target，找出所有可以使数字和等于target的组合，同一个数字可以无限次重复选取。

这道题为什么经典？因为“同一个数字可以无限重复取”这个条件，让选择列表的生成方式发生了变化——每层递归都可以继续选当前数字，也可以跳到后面的数字。这种细节很容易让人第一次写错，但恰恰是理解“选择列表如何变化”的最佳素材。

以candidates = [2, 3, 6, 7]，target = 7为例，决策树怎么画？根节点是空路径，当前目标值是7。第一层可以选2、3、6、7四个数字：

• 选2，剩余目标5，继续往下选；
• 选3，剩余目标4，继续往下选；
• 选6，剩余目标1，继续往下选；
• 选7，剩余目标0，直接命中，得到一个组合[7]。

从选2这个分支继续展开，可以再选2、3、6、7。选2之后剩余目标3，再选2等于7，命中组合[2, 2, 3]；选3直接等于7，命中组合[2, 3, 2]——注意这里问题来了，[2, 3, 2]和[3, 2, 2]其实是同一个组合，只是顺序不同。

为了避免这种重复，必须控制“只能往后面选”。具体做法是传递一个start参数，当前层只能从start位置开始遍历，下一层的start不能小于当前选择的索引。这样组合的顺序就固定是从小到大，不会出现同一个组合的不同排列。

2.2 完整代码与关键剪枝细节

明确了决策树和控制顺序的逻辑，代码就容易写了：

def combinationSum(candidates, target): res = [] path = [] candidates.sort() # 排序是为了后续剪枝 def backtrack(start, remain): if remain == 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remain: break # 剪枝：当前数字已经超过剩余目标值，后面更大，直接退出 path.append(candidates[i]) backtrack(i, remain - candidates[i]) # 注意这里是i，不是i+1，允许重复选当前值 path.pop() backtrack(0, target) return res

这段代码里有几个点需要重点解释。

第一，backtrack(i, remain - candidates[i])里传的是i而不是i + 1。因为题目允许同一个数字无限次使用，所以选了当前这个数字之后，下一层还可以继续从它开始。如果是“每个数字只能用一次”的变体题，这里就要改成i + 1。这个传参差一个1，就是两道完全不同的题目。

第二，排序后的剪枝非常巧妙。因为数组从小到大排过序，当发现candidates[i] > remain时，后面的数字只会更大，都不可能凑出目标值，所以直接break跳出循环，而不是continue。这一步能把很多无效分支直接砍掉，在数据量大时性能差异非常明显。

第三，path.pop()的位置一定在递归返回之后。这个顺序不能乱，先撤销选择再进入下一轮循环，才能保证每轮循环的path状态是干净的。

2.3 为什么这样写能避免重复组合

我见过很多新手问：为什么我写出来的代码会输出[2, 2, 3]和[2, 3, 2]两个重复组合？问题就出在每层递归的选择列表上。

如果每层递归都从头遍历整个candidates，确实能把所有排列都搜出来，但题目要的是组合，组合是不区分顺序的。start参数的作用就是硬性规定：当前层只能从start及之后的位置选择，后一层不能选前面的数字。这样搜索出来的所有结果，数字顺序永远是从小到大排列的，天然就过滤掉了重复。

用一个形象的类比：组合是“班委当选名单”，谁先站上去不重要，名单上有什么人决定了最终结果；排列是“出场顺序”，换一个站法就算一种新情况。回溯模板里带start参数，就是告诉程序“你只能往队伍的后面挑人，不能回头再挑已经看过的人”。

3. 全排列与N皇后：两类经典变体如何套用模板

3.1 全排列：used数组的另一套玩法

组合问题用start控制顺序，排列问题则是另一个套路。全排列要求的是[1, 2, 3]的每一种排列都要输出来，这意味着每一层都可以从所有数字里选，只是不能用已经用过的数字。这时候就需要引入一个used数组来标记哪些数字已经被选了。

LeetCode 46题全排列标准写法：

def permute(nums): res = [] path = [] used = [False] * len(nums) def backtrack(): 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]) backtrack() path.pop() used[i] = False backtrack() return res

这里跟组合问题最大的区别是：递归函数不需要传start参数，因为每一层的选择列表都是“所有未使用的数字”。而used[i] = True和used[i] = False这两行，就是另一个维度的状态重置——path.pop()重置的是路径数据，used[i] = False重置的是选择标记，两个缺一不可。

如果数组里有重复数字，比如[1, 1, 2]，直接套用上面代码会输出重复排列。去重的思路是先排序，然后在循环里加一个判断：如果当前数字和前一个数字相同，并且前一个数字还没被使用过，就跳过。这个剪枝条件看起来有点绕，但它背后的原理是：重复数字之间谁先被选不重要，强制只有前一个被用了，后一个才能被选，这样重复排列就不会出现了。

3.2 N皇后：棋盘类问题的状态管理

N皇后是回溯里天花板级别的经典题，因为它的“状态”不是一维数组，而是二维棋盘。题目要求在一个n × n的棋盘上放置n个皇后，让它们互相不能攻击。皇后可以横走、竖走、斜走，所以每一行、每一列、每一条对角线上都只能有一个皇后。

由于每一行只能放一个皇后，可以天然地用“逐行放置”的递归策略，每层递归只处理一行，递归深度就是棋盘行数。需要额外维护的是三组标记：已占用的列、主对角线、副对角线。这里有一个高中数学知识很方便：主对角线上的所有格子满足行 - 列为同一个常数，副对角线上的格子满足行 + 列为同一个常数。所以用集合维护这这两个差值就能秒判斜线冲突。

def solveNQueens(n): res = [] cols = set() diag1 = set() # 行 - 列 diag2 = set() # 行 + 列 board = [['.'] * n for _ in range(n)] def backtrack(row): if row == n: res.append([''.join(r) for r in board]) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue cols.add(col) diag1.add(row - col) diag2.add(row + col) board[row][col] = 'Q' backtrack(row + 1) board[row][col] = '.' cols.remove(col) diag1.remove(row - col) diag2.remove(row + col) backtrack(0) return res

注意这里的状态重置不只是board[row][col] = '.'，还包括三个集合里的标记。你可能会问，diag1和diag2里存的会不会因为不同行的值重复而冲突？数学上不会，因为同一对角线上的所有格子，行 - 列或行 + 列是完全相同的值，不同对角线自然对应不同值。这也是为什么可以用集合来判重。

我见过有个初学者在这里踩坑：他只重置了棋盘和列集合，忘了重置对角线集合，结果第二个方案死活出不来。调试半天发现对角线集合里残留了上一轮的数据，下一轮的判断全被污染了。所以N皇后这道题，特别适合用来检验你是否真正理解了“撤销操作要跟做选择一一对应”这个原则。

3.3 三类经典问题的对比总结

把上面三道题放在一起看，回溯模板的三种常见变化就很清楚了：

掌握这三类题目的套路，回溯题基本就拿下一大半了。剩下的变形题，比如分割回文串、复原IP地址、括号生成，本质都是“选择列表怎么构建”的问题，换汤不换药。

4. 剪枝优化：把指数级搜索从“能跑”变成“跑得快”

4.1 剪枝的三种常见思路

回溯本质上是一种暴力枚举，时间复杂度通常是指数级的。但这不代表我们只能傻乎乎地从头搜到尾，剪枝是回溯算法里极其关键的一步，直接决定代码能不能在题目给定的时间限制内跑完。

最常见的剪枝思路有三种。

第一种是可行性剪枝。就是当某个选择明显不可能通向合法结果时，直接跳过。比如组合总和里，当前数字大于剩余目标值时直接break；N皇后里，当前列和对角线已经冲突时直接continue。这类剪枝逻辑通常写在循环体最前面，是每道题都会用到的标配。

第二种是排序剪枝。很多组合类题目，如果先对数组排序，可以让可行性剪枝更加高效。组合总和里先排序，才能保证一旦遇到candidates[i] > remain就一定能break；如果不排序，后面可能还有小数字，只能continue，剪枝效果差很多。这也是为什么我会在代码开头默默加上一行candidates.sort()。

第三种是重复性剪枝。当输入数据里有重复元素时，通过排序后比较相邻元素来去重。比如组合总和 II（每个数字只能用一次）里，同一个数字在某一层只要被搜索过一次，后面相同的值就没必要再搜了。这类剪枝写起来最常见的问题是used[i-1]或i > start的条件写错，导致要么没去重，要么把所有结果都剪没了。

4.2 优化案例：组合总和II的去重剪枝

组合总和 II 是组合总和的直接变体：candidates里有重复数字，每个数字只能用一次，结果不能包含重复组合。这道题把“排序 + 去重 + 剪枝”三个技巧全考了，我建议你一定要亲手写一遍。

def combinationSum2(candidates, target): res = [] path = [] candidates.sort() def backtrack(start, remain): if remain == 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remain: break if i > start and candidates[i] == candidates[i - 1]: continue path.append(candidates[i]) backtrack(i + 1, remain - candidates[i]) path.pop() backtrack(0, target) return res

关键的差异点有三个：一是递归参数从i变成i + 1，因为每个数字只能使用一次；二是去重条件是i > start and candidates[i] == candidates[i - 1]，这个条件保证的是“在同一层循环里，如果当前数字和前一个数字相同，就跳过”，但不同层之间不受影响。

这里最让人困惑的就是为什么是i > start，而不是i > 0。原因在于表达的是“同一层的兄弟节点之间不能重复”，而不是“所有递归深度都不能重复”。如果写成i > 0，会把不同层里的合法结果也误杀了。举个例子，candidates = [1, 1, 2]，目标值是4，合法结果有[1, 1, 2]。当第一层选了第一个1，第二层选第二个1是合法的，因为这是不同层的选择。去重只应该发生在同一层里：第一层如果已经尝试过选1，再遇到第二个1就不该选了，因为两条分支的结果会完全一样。

调试这类题目时，最简单的验证方法就是先画决策树，标出哪一层重合了，再对着代码看剪枝条件。等你把这一题彻底吃透，回溯的基本功就非常扎实了。

5. 回溯代码踩坑实录：最常见的Bug与排查技巧

5.1 三个高频Bug的现象与修复方式

学了原理和模板，真正动手刷题的时候还是免不了踩坑。我前前后后帮人调试过不少回溯代码，发现大家翻车的点惊人地一致。整理成一张速查表，方便你以后对着排查。

第一个Bug是最容易自己发现的，因为输出结果看起来很诡异，所有结果都一模一样。第二个Bug则隐蔽得多，尤其当输入数据里出现重复时，需要你静下心去检查“去重条件”和“选择列表生成规则”。第三个Bug我最想强调：回溯的撤销操作必须和做选择一一对应。如果你在循环里写了path.append()但递归返回后忘了pop()，那么下一轮循环的path永远是错的，而且错误会像滚雪球一样累积，越往后越离谱。

5.2 我的调试三板斧

回溯算法的代码量不大，但递归和状态变化让人很难直接看出哪里错了。我自己的调试方法基本就是三板斧，效率非常高，分享给你。

第一招，小规模用例跑一遍。遇到全排列就试[1, 2]，遇到N皇后就试n = 4，遇到组合总和就找一组答案数量少的数据。小规模条件下，你自己手算就能列出所有正确结果，拿代码输出跟手工结果逐一对比，很快就能锁定问题在哪一层。

第二招，在递归入口和出口打印关键变量。比如打印当前层数、start 参数、path 的内容。回溯的本质是树的深度优先遍历，看到打印结果你就能直观感受递归是怎么一层层往下走、又一层层退回来的。很多时候看到路径的推进和回退轨迹，问题瞬间就明白了。

第三招，刻意检查撤销操作是否完整。这是我养成的一个习惯：在写回溯代码时，动笔之前先数一数“做选择”写了几个动作，那么“撤销选择”就一定要写几个对应的动作。比如N皇后里做了board[row][col] = 'Q'、cols.add(col)等操作，撤销时就得对应恢复棋盘、从集合删除。少一个都不行。

配套的还有一种排查思路：如果你不确定撤销操作和做选择是否匹配，可以在写完递归调用后，把函数里所有状态变量的值用print打出来，手动模仿一次递归流程，走一两步就能发现问题出在哪。

说实话，回溯算法是我觉得“会者不难、难者不会”的典型代表。一旦你把决策树模型和状态重置这两个概念彻底想通，以后遇到任何回溯题，写出来的代码几乎都是同一副面孔：先判断结束条件，再 for 循环做选择，然后递归，最后撤销选择——四步走完，收工。

我自己在带项目的时候也有一条依葫芦画瓢的经验：遇到枚举所有方案、所有路径、所有组合的需求，先别急着写代码，在纸上画一棵决策树，然后把树上的每一层对应成递归函数的每一层，最后一个通用模板直接套上去，问题基本就解决一大半了。剩下的剪枝和去重，都是在理解了这棵树之后，才能在正确的位置加正确的条件。

最后再分享一个小技巧：刷回溯题，我建议你每天固定只做同类型的两三道，连续刷一周。你会发现到后面根本不用过脑子，代码条件反射就写出来了。这种“肌肉记忆”对找回溯代码的写感特别有效。等你的手感稳定之后，再变化一些条件——允许重复选、不允许重复选、结果去重、顺序敏感，每改一个条件，你就顺手推导一下决策树怎么变，慢慢就能举一反三了。