回溯算法入门：从全排列到N皇后的完整思维框架

第一次见到回溯题的时候，我整整一个下午没缓过来。题目是全排列，第一反应是三层循环套上去，结果输入一变长的就崩了；后来知道标准做法只用递归，满打满算十几行代码。奇怪的是，代码我可以默写出来，但稍微换个题就不会了——组合还好，子集也行，一上N皇后直接傻眼。当时我还没意识到，回溯真正的门槛根本不在代码，而在“你怎么看待这棵树”。

这就是标题里“算法学习day25-回溯”的含金量。第25天刚好是我刷题计划中从“会背模板”到“会设计状态”的分水岭：回溯是什么、怎么剪枝、怎么去重、复杂度怎么算，几乎全在这几天里被打通了。这篇文章不打算从高深的理论讲起，而是把我自己踩过的坑、用顺手的写法、以及从全排列到数独的完整推导路径全部整理出来。适合刚吃透递归、正准备啃回溯的读者，也适合刷过一批回溯题但总觉得差了点什么的朋友。

1. 回溯到底是什么：从走迷宫到解空间树

1.1 一个所有人都走过的直觉模型

回溯的“回溯”两个字，本身就来自走迷宫。你在一个岔路口选了一条路，走了一段发现是死胡同，于是退回到刚才的岔路口，换一条路再试。电脑干的事和这个一模一样，只不过它把“岔路口”建模成了递归中的每一次调用，把“试路”建模成了循环里的每一个选择。

最容易被忽略的一件事是：回溯不是某种新的算法套路，它就是在状态空间树上做深度优先遍历，只不过在遍历的过程中必须带着“撤销”这个动作。走迷宫时你没有把走过的路从地图上抹掉，是因为地图是固定的；但在算法题里，如果你试了1这条分支，回到分岔点时却不把1从路径里拿掉，那下一条分支就会变成1,2、1,3，而不是干净的2、3。所有写错的回溯代码，十有八九都是忘了这一步。

我后来特别喜欢用“试螺丝刀”来类比：你面前有一把锁，手里有六把看起来差不多的螺丝刀，你得一把一把试，试完一把就放回原位再拿另一把。放回原位，就是回溯里的撤销操作。代码里对应的动作是path.pop()，是used[i] = False，这两个操作少一个，整棵树就被污染了。

1.2 解空间树：一眼看穿递归在干什么

如果你把一次回溯算法的完整执行过程画出来，会得到一棵树。树的根是空状态，每个节点是一次递归调用，节点下面挂着当前层可做的所有选择。拿全排列举例，nums = [1,2,3]时：

• 根节点：路径为空
• 第一层：可以选择1、2、3，生成3个分支
• 第二层：选择1之后，下一层只能选2、3；选择2之后，下一层只能选1、3
• 第三层：填满3个位置，到达叶子，记录结果

这棵树就是“解空间树”。理解了这棵树，你就理解了回溯里几乎所有术语：递归的深度等于路径长度，for循环是在枚举当前层的孩子，used数组和startIndex是在决定当前层能选哪些孩子，剪枝是发现某个孩子下面不可能有答案时直接不往那边走，去重是发现两个孩子长成一样于是只留一个。

我在第25天之前一直不懂“回溯 = 深度优先搜索”这句话。总觉得DFS是图算法，回溯是数学题。后来才想明白，图里的DFS遍历的是图结构，回溯遍历的是“解状态”组成的虚拟树。两者代码骨架几乎完全一样，只是回溯在每个节点上多了记录和撤销的步骤。这么一对应，之后学记忆化搜索、学状态压缩，全都是顺水推舟的事。

1.3 回溯和暴力枚举的边界在哪里

有人问：回溯不就是暴力吗？把每个组合都枚举一遍，复杂度还不是指数级？这么说对也不对。

暴力枚举意味着你提前知道要嵌套几层循环，比如“三个数里选组合”你写三层循环，“四个数”写四层。可一旦n变成变量，循环层数写不出来，暴力枚举直接失效。回溯用递归来代替循环层数，本质上是用递归的栈深度去模拟那个不确定的嵌套层数。这个能力让回溯能处理n不固定、约束复杂、必须边走边判断的题目，比如N皇后、数独、括号生成。

所以更准确地说，回溯是系统化的暴力枚举，它把“枚举”这件事做成了可伸缩的模板。代价是时间复杂度仍然很糟糕，所以才需要下一章严格训练的剪枝和去重。没有剪枝的回溯几乎是不可用的，这是所有从模板入门回溯的人，迟早会撞上的墙。

2. 回溯模板与入门三件套：全排列、组合、子集

2.1 统一模板：选择-递归-撤销三步曲

回溯题不管怎么换皮，代码骨架都是同一个。我现在的习惯是先写出这个模板，再把具体题目的状态、出口、剪枝条件填进去：

def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 当前可做的所有选择: 做选择（更新路径和状态） backtrack(路径, 新的选择列表) 撤销选择（恢复路径和状态）

用伪代码写出来只有四行，但其中“记录结果”和“撤销选择”这两步最容易翻车。记录结果时，Python里如果你写res.append(path)，之后path一变，res里存的东西也跟着变——因为path是同一个列表对象。必须写成res.append(path[:])做浅拷贝，或者存一个拼接好的字符串。至于撤销选择，第五章我会专门列一个避坑清单。

这个模板真正重要的地方在于：你必须明确“路径”、“选择列表”、“结束条件”三样东西分别是什么。全排列的选择列表是“所有还没被用过的元素”，组合的选择列表是“当前下标之后的所有元素”，子集的选择列表则是“当前下标之后的所有元素，且在每一层都记录当前路径”。三句话就能看出它们之间的差异在哪里。

2.2 全排列：用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() path.pop() used[i] = False dfs() return res

这里used数组就是“选择列表”的落地实现。它记录的是“下标是否被占用”，而不是“值是否被用过”——这个区别在有重复元素的排列里会变得极其关键（第四章再展开）。递归结束后，used[i] = False被称为“回溯”的经典动作，千万别漏。可以用一个临时数组验证：把这个赋值注释掉，结果会变成什么呢？输出会非常离谱，同一层的每个分支都会沿用上一分支用过的元素，最终路径长度暴涨，递归永不结束或结果疯狂重复。

2.3 组合和子集：startIndex承担了什么角色

组合题combine(n, k)让你在1到n里选k个数，不考虑顺序。如果不做任何限制，[1,2]和[2,1]会同时出现，但那在组合语义下是同一个东西。解法是用一个start参数，规定下一层只能从i+1开始取数，这就叫“不回头”——后面的选择不能在它前面再选。

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

子集题则是组合的变体：所有长度的组合都要。所以它不在叶子才记录，而是在每个节点都记录当前路径。另一种理解是，把“选或不选每个元素”展开成二叉树，每次递归可以走两条路：选当前元素，或不选。但用start版本的写法更统一，代码也更紧凑：

def subsets(nums): res, path = [], [] def dfs(start): res.append(path[:]) # 每个节点都记录 for i in range(start, len(nums)): path.append(nums[i]) dfs(i + 1) path.pop() dfs(0) return res

2.4 三者的状态与出口差异对照

把三道题放在一起对比，表格比文字直观得多：

这张表我每次做回溯题都会在心里默念一遍。题目一变，先判断它是排列还是组合还是子集，再决定用used还是start。把两者混用是目前刷题社区里最常见的错误：有人写组合却在递归里从头循环，结果同一组合出现多次；有人写排列却传了个start，结果能选的元素越来越少，答案直接少了一大半。

3. 剪枝：回溯从“能跑”到“跑得动”的关键

3.1 剪枝的本质：提前砍掉必死的子树

回溯的时间复杂度天然是指数级的。全排列n!、子集2^n，当n稍微大一点，不剪枝的版本会慢得让人怀疑人生。剪枝要做的事很简单：在遇到某个节点时，如果能判断出这个节点下面的所有分支都不可能产生合法答案，就不进入这些分支。相当于走迷宫时你看到地上标着“此路不通”，于是连试都不想试，直接换路。

但这里有个容易误解的点：剪枝的前提是你有足够的判断能力。判断能力来自题目约束。比如组合总和的题combinationSum，目标值target，如果当前累加的和已经超过target，那么继续往下加正整数只会更大，可以整体放弃；比如N皇后，如果某列已经放了皇后，那这一列的所有格子都不用再试。判断不了的分支，只能老老实实走完。

3.2 两类常见剪枝：约束剪枝与限界剪枝

第一类是约束剪枝，本质是“不合法就不走”。第二类是限界剪枝，本质是“即使能走到底，也没有继续的价值”。我把它们分开记，是因为写代码时它们的表现形式不同：约束剪枝一般写在for循环里作continue条件，限界剪枝一般配合排序作break。

拿组合总和I来展示限界剪枝：

def combinationSum(candidates, target): res, path = [], [] candidates.sort() def dfs(start, cur_sum): if cur_sum == target: res.append(path[:]) return for i in range(start, len(candidates)): # 剪枝：candidates升序，后边的更大，不需要再试 if candidates[i] > target - cur_sum: break path.append(candidates[i]) dfs(i, cur_sum + candidates[i]) path.pop() dfs(0, 0) return res

这里排序是剪枝的前提。没有排序，你没法确定后面元素都大于当前元素，自然不能用break提前结束整层循环。这是很多教程不会单独提醒的细节：限界剪枝常常和排序绑定出现，把排序写在递归外面的原因就在这里。顺序写反了，剪枝条件不仅不成立，还会把正确答案直接剪掉，程序还不报错，调试起来特别难受。

3.3 剪枝翻车实录：我把合法解剪掉了

剪枝写错方向这件事，我亲身经历过一次。当时写N皇后，检查列和对角线的代码是：

if cols[col] or diag1[row + col]: continue

漏掉了副对角线diag2[n - 1 + row - col]。结果程序跑得飞快，答案数量却比正常的n=4少了两套。功能缺失完全不报错，只有把答案和标准输出对比才能发现。更隐蔽的是另一种错误：把对角线索引公式的边界算错，导致某些列明明合法却被当成冲突跳过。这种问题没有任何报错，纯粹是逻辑层面错了。

从那以后我养成了两个习惯。第一个是写剪枝时，一定先画一个最小样例的状态树，把剪枝条件的每一步对着题目的约束逐条过一遍。第二个是默认相信自己会写错，写完就用最朴素的暴力解跑一遍小数据做对拍。回溯题的剪枝是加分项，但前提是功能必须正确。先保证不剪枝版本能得出正确答案，再加剪枝优化，这个顺序不能反过来。

4. 去重陷阱：为什么答案里会出现重复项

4.1 重复的两个来源

去重是整个回溯里最绕的部分，因为它要区分两种完全不同的“重复”。

第一种是顺序层面的重复。组合题里[1,2]和[2,1]是同一个答案，这个用startIndex解决，前面已经提到。

第二种是相同值的重复。输入数组nums = [1, 1, 2]时，元素是有相同的。如果还按普通排列去写，两个1都会被当成独立的可选项，于是[1_1, 2]和[1_2, 2]会同时出现在结果里——它们位置不同、语义不同，但在人眼里都是[1, 2]。题目要求去重的话，就要决定：这两个1在同一层只能被选一次。

很多初学者会把这两种重复混为一谈，一看到“去重”就在结果里加set，那是下策。真正清晰的思路是先想清楚：重复来自同一路径的不同顺序，还是来自同一数值被当成不同元素。前者用startIndex，后者用排序加used数组。

4.2 三种去重方案的功能对比

假设题目是“有重复元素的排列，输出不重复的排列”，常见有三种处理方式：

第三种是我推荐的方案。它能避免大量无效递归，在n较大时优势明显。代码长这样：

def permuteUnique(nums): res, path = [], [] nums.sort() 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-1]为False if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue used[i] = True path.append(nums[i]) dfs() path.pop() used[i] = False dfs() return res

4.3 排序去重的核心细节：为什么是not used[i-1]

上面这行去重判断，是整个回溯里最容易被写反的一行。许多人背下来代码，却没搞懂为什么是not used[i-1]而不是used[i-1]。

关键在于：nums[i] == nums[i-1]意味着当前这个值和前一个值相等。现在分叉成两种情况。

如果used[i-1] == True，说明前一个相同的值还在当前这条路径上，比如路径已经选过第一个1，现在要选第二个1，这是合法的、正常的树枝上的连续选择。如果这时候把分支剪掉，[1, 1, 2]这种答案永远出不来。

如果used[i-1] == False，说明前一个相同的值已经被用过又被撤销了。这意味着上一棵子树已经完全走完，现在回到了同一层的下一个兄弟节点。此时再选这个相同的值，就会生成和上一棵子树一模一样的路径。这才是应该剪掉的情况。

所以判断条件必须是“前一个相同值不在当前路径上时，跳过当前值”。用not used[i-1]表达的就是这个语义。这个细节也是面试或文档里高频出现的追问点。理解它之后，所有排序去重题都能无障碍套用。

5. 从模板到实战：N皇后、数独和更复杂的状态设计

5.1 N皇后：一维路径装不下二维棋盘

全排列、组合、子集这三件套练熟之后，我一度以为回溯没什么大不了。N皇后直接把我打回原形——因为它的路径不再是一个简单列表，而是一个棋盘；递归的每一层也不再对应“选择列表里的一个下标”，而是对应棋盘的一行。

我推荐的写法是按行递归。一行放一个皇后，递归函数传入当前行号row，在for col in range(n)里尝试当前行的每个列位置。只要能通过列、主对角线、副对角线三个约束检查，就把皇后放下再进入row + 1。这样做的好处是，递归深度固定等于n，每一层只负责一行，状态记录也只剩三个额外数组：

def solveNQueens(n): res, board = [], [['.'] * n for _ in range(n)] cols = [False] * n diag1 = [False] * (2 * n - 1) # 主对角线 row + col 范围 0..2n-2 diag2 = [False] * (2 * n - 1) # 副对角线 n - 1 + row - col def dfs(row): if row == n: res.append([''.join(r) for r in board]) return for col in range(n): if cols[col] or diag1[row + col] or diag2[n - 1 + row - col]: continue cols[col] = diag1[row + col] = diag2[n - 1 + row - col] = True board[row][col] = 'Q' dfs(row + 1) board[row][col] = '.' cols[col] = diag1[row + col] = diag2[n - 1 + row - col] = False dfs(0) return res

N皇后教我的最重要一课是：回溯的状态不一定只有一个列表，它可以是多个并行状态。路径是棋盘，状态是三个布尔数组，两者要一起“做选择”和“撤销”。很多难一点的回溯题都是这个模式——比如数独需要维护行、列、宫三组集合，本质完全一样。

5.2 数独：找到第一个空格直接开搜的写法

数独比N皇后更接近“搜索”的原始形态，因为它不是一行一行往下填，而是需要不断跳转到下一个空格。一种简单稳定的写法是：每层递归用双重循环找到第一个空格，再尝试填入1到9的所有数字，填完继续递归；如果所有数字都试过还是不行，就返回上一层把当前数字清掉。

这里要特别注意的是，数独的“剪枝”不是锦上添花，而是正确性的一部分：只有当前数字不冲突，才允许继续往下填。用集合记录行、列、宫内已有数字，冲突检查就变成三个in判断：

def solveSudoku(board): rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] for r in range(9): for c in range(9): if board[r][c] != '.': v = board[r][c] rows[r].add(v) cols[c].add(v) boxes[r // 3 * 3 + c // 3].add(v) def dfs(): for r in range(9): for c in range(9): if board[r][c] == '.': b = r // 3 * 3 + c // 3 for num in map(str, range(1, 10)): if num not in rows[r] and num not in cols[c] and num not in boxes[b]: board[r][c] = num rows[r].add(num) cols[c].add(num) boxes[b].add(num) if dfs(): return True board[r][c] = '.' rows[r].discard(num) cols[c].discard(num) boxes[b].discard(num) return False return True dfs()

这种层层跳到第一个空格的做法，代码量不多，但对“状态撤销”的要求更高：三个集合里加了什么，递归返回后就要立刻删掉。用discard而不是remove是我个人的习惯，虽然这里添加后必然存在，但写成discard能避免撤销顺序搞错时直接抛异常，调试时少一点崩溃。

5.3 回溯的“亲戚”：记忆化搜索与动态规划

刷到第五周时，我开始遇到一些“长得像回溯”却不能用回溯硬莽的题。比如某个状态在递归中会被反复计算很多次，明明同一个子问题已经算过，回溯还是会重算一遍。这种题的正确解往往是记忆化搜索：在回溯的入口接收一个memo字典，计算过某个状态就直接返回缓存结果。

一个典型的场景是“从起点到终点的路径数量”。第一个版本我用回溯枚举所有路径，n稍微大一点就超时。后来改成memo[(i, j)] = dfs(i, j)的形式，几十行代码变成几行，运行时间从指数级降到线性。这件事给我的启发是：回溯不只是一个个独立题型的代称，它是一种搜索范式。理解了这个范式之后，记忆化、动态规划这些优化手段自然都能接上——你只是不再从零开始设计“怎么枚举”，而是先枚举再想办法避免重复枚举。

6. 复杂度与性能优化：心里有数才能不慌

6.1 时间复杂度到底该怎么估

回溯题面试必问复杂度，但很多人的回答是笼统的一句“指数级”。更专业的说法是：

• 全排列：结果数是n!，每个结果拷贝路径要O(n)，总时间O(n * n!)
• 组合：结果数是C(n, k)，每个结果也是O(k)，总时间O(k * C(n, k))
• 子集：结果数是2^n，每个结果拷贝要O(n)，总时间O(n * 2^n)

一句话总结就是答案个数乘以生成每个答案的平均成本。剪枝可以让这个上界在实际数据上变小，但理论分析通常还是按未被剪枝的情况来写。N皇后更特殊一些，经典回溯的上界是O(n!)，实际因为列和对角线的剪枝，跑得远比这个上界快，但面试里给出O(n!)并说明剪枝影响即可。

6.2 空间复杂度：递归深度和结果集分开看

空间复杂度有两个大头。一个是递归时正在使用的那条路径，占O(递归深度)；另一个是最终存下的所有结果，占O(答案数 * 答案长度)。如果把所有答案都存在内存里，空间往往就比时间更吓人——全排列的n=10时，结果数组就有几百万项。有些题目只要求输出答案数量，那就不要在递归里逐步append到全局列表，而是用一个计数器累加，空间立刻降到O(n)。

6.3 实际优化时应该按什么顺序做

我个人的优化顺序是：先验证正确性，再考虑剪枝，最后才碰常量优化。具体手段从易到难大概是：

1. 排序后结合限界条件提前break，这是性价比最高的一步
2. 检查能否用set或布尔数组代替in list，避免每次选择都遍历
3. 在状态设计上压缩，比如N皇后用位运算标记列和对角线，比布尔数组再快一个常数级
4. 约束条件多的题可以加启发式，比如数独里优先填“可选数字最少”的空格，这是MRV策略，代码会复杂一些但速度提升非常明显

记住一个反直觉结论：很多时候你的回溯慢，不是因为语言慢或者常数大，而是因为剪枝没做对。把无效分支砍掉带来的收益通常是数量级的，比任何微优化都大。

7. 刷完回溯之后：我的避坑清单和一点私货

7.1 五个最容易踩的坑，一个一个查

第一个坑是忘记撤销。递归写完，path.append和used[i] = True都有，但path.pop()或used[i] = False漏了。后果前面已经演示过，建议把“做选择、递归、撤销选择”当成一个整体来记忆。

第二个坑是记录结果时浅拷贝翻车。Python里res.append(path)之后，path后续的任何修改都会同步到res里。正确写法是path[:]或''.join(path)。

第三个坑是排列和组合的状态混用。排列需要used数组从整个数组里选，组合需要startIndex从后面选。两者交叉使用会导致重复或漏解。

第四个坑是剪枝条件剪掉了合法解。这个问题最隐蔽，因为不报错。要养成分步验证的习惯，先用不剪枝的版本在小数据上对拍。

第五个坑是递归出口放错位置。比如数独题把return True/False写在了外层for循环之后，导致递归返回值不能正确传递。遇到这种问题，在纸上写出两个递归深度的调用关系，比盯着代码看半小时管用。

7.2 让思路变清晰的一个训练方法

如果你现在对回溯还是半懂不懂，我强烈建议做这样一件事：找全排列[1,2,3]，手动画一棵三层状态树。每个节点标注“当前路径”，每层标注“可选项”。画完你会发现，所谓“选择列表”其实就是你站在当前节点时能看到的孩子。used数组存在的意义，就是让你在任何一个节点都能准确知道“哪些孩子还能去”。我在day25那天画了整整两页纸，把全排列、组合、子集三棵树并排贴在桌子前面。之后遇到任何回溯题，我第一反应就是“这题的解空间树长什么样”，而不是“这题套哪个模板”。这是一个从背代码到真正理解的分水岭。

7.3 给你的一点私货

如果这一天的学习只能记住一句话，我会记下这句：回溯就是一棵树，你要做的只有三件事，做选择、递归、撤销。剪枝和去重都是在这棵树上做的优化，状态设计决定每一层长什么样，结束条件决定你在哪里摘果子。理解到这层之后，再难的题也不会让你觉得回溯是个黑盒。

至于刷题计划本身，我给的建议是别把回溯和递归分开练。递归是回溯的骨架，回溯是递归的应用。递归吃不透，回溯写再多也只是死记硬背。先把几道经典的递归题搞定，再回头过这一篇的每道例题，你会发现自己忽然就通了。