企业官网建设流程全解析

昨天还在跟排列组合死磕，今天直接进入算法学习 day24，正好轮到回溯这个专题。说实话，回溯这章我从学递归开始就一直绕着走，总觉得“递归里套循环、循环里再递归”太绕，看题解看得懂，自己一写就错。但今天静下心来把决策树画出来之后才发现，它无非就是“暴力枚举 + 状态恢复”，只是以前没人跟我说清楚“为什么每次递归完都要撤销一步”。

这篇内容的核心关键词就两个：算法、回溯。如果你正在为回溯题目发愁，或者准备面试想系统过一遍这个专题，可以直接把这篇当作复习提纲。我尽量把模板、剪枝、去重、常见 bug 一次讲透，最后还会分享我自己的复盘习惯，希望能让你少走点弯路。

1. 回溯算法到底是什么：从暴力枚举到带撤销的深度优先

1.1 暴力枚举和回溯的关系

很多人第一次接触回溯，都会陷入一个误区：觉得回溯是一种很高级、很玄妙的算法。其实你把它理解成“用递归实现的暴力枚举”就够了。

举个例子，给你一个数组 [1, 2, 3, 4]，想选 2 个数组成组合。最朴素的想法是什么？写两层 for 循环，外层选第一个数，内层选第二个数，然后判断一下组合是否重复就行。但如果题目改成“选 k 个数”呢？k 是变量，你不可能在代码里写 k 层 for 循环。这时候就需要一种机制，让同一个函数能代替任意层数的循环，递归刚好能胜任这件事：每一次递归，就相当于进入了一层新的 for 循环。

所以回溯的本质很简单：它用递归实现了“层数不固定的循环”，把所有可能的解全部试一遍，遇到符合条件的结果就记录下来。之所以叫“回溯”，是因为它在尝试完一个分支之后，需要退回到上一个状态，再尝试下一个分支。

1.2 回溯为什么一定要能“回头”

我见过很多初学者，包括我自己最开始，写回溯代码时最大的问题就是：忘了撤销选择，或者不知道怎么撤销选择。

你可以想象自己在走迷宫。你一路往前走，在每个路口选择一条路试探，走到死胡同就退回到上一个路口，换另一条路继续走。这个“退回到上一个路口”的动作，就是回溯。如果你走到死胡同不回头，还在原地继续往下走，那你永远也找不到出口。

放到代码里，这个“回头”的动作就是把当前路径上最后加入的元素移除，把一些标记位恢复成未使用状态。为什么要这么做？因为整个搜索过程共用同一个路径变量，如果你在尝试完 [1,2] 这个分支后不把 2 弹出去，下一次尝试 [1,3] 时，路径会变成 [1,2,3]，结果自然就错了。你可以把它类比成收拾桌子：你尝试完一种摆法，必须把桌面恢复原样，才能继续试下一种摆法。

1.3 回溯解决的典型问题长什么样

回溯擅长处理“在多个候选方案里挑出满足约束条件的组合/排列”这类问题。常见的题型几乎就那么几类。

• 组合类：比如从 n 个数字里选 k 个，或者从一串候选数字里凑出目标值。
• 排列类：比如给一个数组，输出所有可能的排列顺序。
• 子集类：比如给一个不含重复数字的数组，返回它的所有子集。
• 分割类：比如给定一个字符串，把它分割成若干个回文子串，或者恢复成合法的 IP 地址。
• 棋盘类：比如 N 皇后问题、解数独问题。

这些题在力扣上基本都是高频题，而且套路非常统一。你只要把回溯的模板记熟，再掌握几个关键的剪枝和去重技巧，就能解决一大片题目。

2. 回溯三步走：先把标准模板刻进脑子里

2.1 一份可以直接抄的模板

我在学习时最喜欢的做法，是先把一个通用模板背下来，然后在各类题里反复套用。回溯算法的骨架大概是这样的：

def backtrack(路径, 选择列表): if 满足结束条件: result.append(路径[:]) # 注意要拷贝，别直接放进去 return for 选择 in 选择列表: # 做选择 路径.append(选择) # 进入下一层 backtrack(路径, 新的选择列表) # 撤销选择 路径.pop()

这个模板看着简单，但信息量不小。“结束条件”决定了何时收集结果；“选择列表”决定了每一层还能选什么；“做选择”和“撤销选择”是配套动作，必须成对出现。我用一个组合题目的具体版本来展示，它会更直观一些。

2.2 撤销选择这一步为什么不能省

我用最经典的“从 1 到 n 中选 k 个数”来演示。先看一个不完整版本的执行过程，你就明白撤销的重要性了。

假设 n = 3, k = 2，我们从数字 1 开始搜索：

• 第一层选了 1，path = [1]。
• 第二层选了 2，path = [1, 2]，满足长度 2，收集结果。
• 此时如果不把 2 弹出，继续回到第一层尝试选 3，那么 path 还是 [1, 2]，再把 3 append 进去就变成了 [1, 2, 3]，不仅长度超了，还出现了错误的组合。

所以在第二次递归返回之后，必须把最近一次加入的元素弹出去，让 path 回到 [1] 的状态，才能继续尝试 3。这一步就是整个算法的灵魂。很多人看题解时会想：为什么模板里一定要有一行 path.pop()？我删掉试试？我强烈建议你别删，删了之后跑一遍，你会立刻看到一堆脏数据。

这里还有一个细节：有时候你不一定用 path.append 和 path.pop，也可能用字符串拼接，比如 path + str(i)，因为它每次都会生成新的字符串对象，所以天然不会污染原路径。但要注意的是，字符串拼接会带来一定的额外开销，而且如果你用的是可变对象（比如列表），就必须显式撤销。

2.3 模板里的三个参数怎么定

我总结了三个最关键的参数设计点，决定了一个回溯函数能不能写得顺畅。

第一个是“当前路径”。你至少得知道自己现在选了哪些元素，才能判断是否满足条件。路径通常是列表，进入结果时用切片拷贝。

第二个是“可选范围”。组合、子集类问题通常需要一个 startIndex 参数，用来控制每一层从哪个位置开始选。为什么需要它？因为组合不考虑顺序，[1, 2] 和 [2, 1] 是同一个组合。靠 startIndex 可以保证后面的选择永远比前面大，从根源上避免重复。排列类问题则不需要 startIndex，因为 [1, 2] 和 [2, 1] 是两个不同答案，但你需要一个 used 数组来避免同一个元素被重复使用。

第三个是“目标状态”。可能是组合的长度 k，也可能是目标数字 target，还可能是一些位置约束。它决定了什么时候终止递归。比如组合题里 len(path) == k 就是终止条件；组合总和题里 target == 0 就是终止条件。

这三个参数想清楚了，回溯的代码基本就成型了。不要一开始就纠结各种边界情况，先把主路线跑通，再慢慢优化。

3. 三个经典题把模板用熟

3.1 组合问题：n 选 k 的写法与剪枝

题目“77. 组合”，给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

标准做法：

def combine(n, k): res = [] path = [] def backtrack(startIndex): if len(path) == k: res.append(path[:]) return for i in range(startIndex, n + 1): path.append(i) backtrack(i + 1) path.pop() backtrack(1) return res

我画了递归树之后才真正理解这段代码发生了什么。第一层 startIndex = 1，从 1 开始枚举；第二层 startIndex = i + 1，保证后面的数一定比前面大。比如第一层选了 2，第二层只能从 3 往后选，就不会出现 [2, 1] 这种重复组合。

接着是剪枝。以 n = 4, k = 3 为例，当 path = [1] 时，我们还需要再选 2 个数。此时如果 i = 4，剩余可选元素为 0，明显凑不满 3 个，所以不必进入这个分支。剪枝的条件是：i <= n - (k - len(path)) + 1。这里的 k - len(path) 表示还差几个数，n 减去这个差值再加 1，就是 i 能取到的上限。改造后的循环是这样：

for i in range(startIndex, n - (k - len(path)) + 2): # 注意 range 右开，所以要 +2 才能包含边界值

很多题解里把这一步写得像魔法公式，其实道理很简单：你数一数当前剩余可用的元素个数，如果连“还需要的个数”都不够，直接跳过。这个剪枝对大数据量的组合题目提升非常明显。

3.2 全排列：用 used 数组标记已选元素

题目“46. 全排列”，给定一个不含重复数字的数组，返回所有可能的全排列。

组合和排列最大的区别在于：组合不在乎顺序，排列在乎顺序。因此全排列每一层都能从头开始选，但必须排除已经放进 path 的元素。used 数组就是干这个的。

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

注意，这里“做选择”的动作有两个：把元素加入 path，以及把 used[i] 置为 True。“撤销选择”也要配套两个动作：把元素弹出 path，以及把 used[i] 置为 False。少了哪一个都不行。

第一次写全排列的时候，我总觉得 used 数组是多余的，认为用 startIndex 也能避免重复。试了一下立刻发现问题：如果用 startIndex，第二层就只能从当前下标后面开始选，这样得到的就不是排列，而是一个个递增的子集，[1,2,3] 和 [2,1,3] 这类顺序不同的结果根本不会被输出。所以排列和组合，参数模型的差异是本质性的，一定要分清楚。

3.3 子集问题：每一层递归都要收集结果

题目“78. 子集”，给定一个不含重复元素的整数数组，返回该数组所有可能的子集。

子集问题跟组合、排列又有点不一样。组合和排列都是收集叶子节点，子集问题要求收集所有节点，包括根节点（空集），也包括中间状态。

def subsets(nums): res = [] path = [] def backtrack(startIndex): res.append(path[:]) # 每次进入递归都收集一次 for i in range(startIndex, len(nums)): path.append(nums[i]) backtrack(i + 1) path.pop() backtrack(0) return res

你可以观察这个代码的执行顺序：第一次进入 backtrack 时，path 是空集，把空集加入结果；然后选 1，把 [1] 加入结果；再选 2，把 [1,2] 加入结果；选 3，把 [1,2,3] 加入结果；返回后选 3，把 [1,3] 加入结果…… 整棵树的每一个节点都被收集到了。

子集问题的“终止条件”其实隐藏了：for 循环自然结束就返回。这也是很多初学者容易懵的地方，因为模板里没有 if 结束条件，代码照样能跑。如果你之前只会写带显式终止条件的回溯，第一次看到这种写法，可能会有点不适应。我的建议是，你把这个版本画一遍递归树，立刻就能理解：在这个问题里，节点本身就是答案，不需要等到叶子。

4. 剪枝和去重：让回溯从“能跑”到“能快”

4.1 剪枝的本质：提前跳过不可能的分支

回溯最大的缺点就是慢，因为它本质上是在枚举所有可能。一旦数据规模变大，不剪枝的回溯会指数级爆炸。剪枝的目的，是在递归还没进入某个分支之前，就判断这个分支不可能产生合法结果，直接跳过。

判断要不要剪枝，我心里一般有三个问题：

• 第一，当前状态还满足约束条件吗？
• 第二，继续走下去还凑得齐需要的元素数量吗？
• 第三，这个分支和已经尝试过的分支，是否会产生重复结果？

这三个问题对应三类剪枝：合法性剪枝、数量剪枝、去重剪枝。

以组合问题为例，数量剪枝我们已经见过：剩余可选元素不够的时候，直接不进入循环。合法性和数量剪枝往往是一起的，比如组合总和问题里，如果当前 target 已经小于 0，就说明前面选的数字太多，这棵子树没有必要再走了。

剪枝写多了之后，你会形成一种直觉：随便看一道回溯题，先写一个不带剪枝的版本保证正确，再根据输入规模的范围去补剪枝条件。千万不要一上来就剪枝，那样很容易把合法结果一起剪掉，排查起来比不加剪枝还要麻烦。

4.2 组合总和里的数值剪枝

题目“39. 组合总和”，给你一个无重复元素的候选数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。关键规则是 candidates 中的同一个数字可以无限制重复被选取。

这个题我刚学的时候犯了一个错：一直想着怎么去重，却先忽略了最简单的剪枝。实际上，如果当前 target 减去候选数字之后已经小于 0，那么这个分支肯定不符合要求。标准写法大概是这样的：

def combinationSum(candidates, target): res = [] path = [] def backtrack(startIndex, remaining): if remaining == 0: res.append(path[:]) return for i in range(startIndex, len(candidates)): if remaining - candidates[i] < 0: continue path.append(candidates[i]) backtrack(i, remaining - candidates[i]) path.pop() backtrack(0, target) return res

这里有两个细节值得专门记一下。第一个细节：递归时传入的是 i 而不是 i + 1，因为题目允许同一个数字重复使用。第二个细节：即使允许重复，也不能让下一次递归从头开始选，否则会出现 [2, 2, 3] 和 [2, 3, 2] 这种顺序不同但实际一样的结果。startIndex 仍然控制着选择范围，只是不递增而已。

如果你把这个题的 candidates 先排个序，还能让剪枝更高效：一旦遇到剩余值减不过去的元素，后面的元素更大，肯定也都减不过去，可以直接 break 跳出循环，而不是 continue。说白了，continue 是跳过当前这个，break 是后面全都不看了。

4.3 排序去重到底去的是什么

题目“40. 组合总和 II”，和上一题的区别是：候选数组里可能有重复数字，而且每个数字在每个组合中只能使用一次。这就涉及一个高频考点：如何去重。

我当初困在这个问题上很久，后来才明白一个核心原则：“同一树枝上可以使用重复元素，同一层上不能使用重复元素。”

什么叫同一层？比如 candidates = [1, 1, 2, 5]，要求在每一层选择一个数。第一层的两个 1，分别作为起点的时候，会生成几乎一样的组合，比如 [1, 2] 和另一个 [1, 2]。从整棵递归树来看，它们是同一层上产生的重复分支，所以必须跳过第二个 1。

什么叫同一树枝？比如在一条路径上选了第一个 1，之后还可以选第二个 1，因为数组中确实有两个 1，[1, 1] 是合法组合。这两个位置处于递归的不同深度，属于同一根树枝上的不同节点，所以不需要去重。

用一个方法就能同时满足两种需求：先排序，然后在循环里判断：

if i > startIndex and candidates[i] == candidates[i - 1]: continue

注意条件里 i > startIndex 是关键。它表示：如果当前元素和前一个元素相同，并且前一个元素是本层已经枚举过的起点，就跳过。为什么不用 used 数组？其实 used 也可以，但你得理解 used 判断的本质：当前 used[i - 1] == False，说明同一层的前一个相同元素已经“撤销”过了，那当前分支就是重复分支；而如果在树枝上，used[i - 1] 会是 True。两种写法都能过，但很多人会把排序去重和 used 去重混在一起写，结果把自己绕晕。我的建议是：先掌握“排序后按 i > startIndex 判断”这种最简单的方法，把题目跑通之后再去研究另一种。

5. 踩坑实录：回溯题最常见的六个问题

5.1 结果重复、结果缺失、结果被篡改

我在刷回溯专题的两天里，几乎把所有经典 bug 都踩了一遍。下面这些情况，如果你在运行题目时遇到了，可以直接对照排查。

第一种，结果被篡改。表现为最后输出的每个结果都一样，而且是空的或者只剩最后一组。最经典的错误是 res.append(path) 而不是 res.append(path[:])。path 是同一个列表对象，后面每次 pop、append 都在改它，所有已经存进去的“结果”其实都指向这个对象，最后自然全部变成同一副模样。解决办法就是用切片生成一个副本。

第二种，结果重复。组合类问题里，没有用 startIndex，或者 startIndex 控制错误，就会出现 [1, 2] 和 [2, 1] 同时存在。排列类问题里，如果没加去重，重复元素会让同一排列出现多次。解决方案就是前面说的：组合用 startIndex，重复元素排序去重。

第三种，结果缺失。最常见的原因是剪枝条件太狠。比如组合题里把 i <= n - (k - len(path)) + 1 写成了 i < n - (k - len(path)) + 1，等于把边界合法的那个数也剪掉了。或者组合总和的去重条件写成了 if candidates[i] == candidates[i - 1] continue，连同一树枝上的合法重复也跳过了。遇到这种问题，先把剪枝代码临时注掉，跑通再慢慢加回来，通常能快速定位。

5.2 递归无限深和性能瓶颈

递归无限深通常是因为终止条件写错了。比如组合总和问题，如果在递归里 target 始终不变，并且 startIndex 也不变，就会无限调用自己。演示一下：path 加了数字之后 remaining 没减少，下一层还是同样的 remaining，再选同一个数字，永远无法走到 remaining == 0。这种情况会在力扣上报“RecursionError”或者直接超时。排查技巧很简单：在函数入口打印 path，看看执行流程是不是在无限循环。

性能瓶颈也要提一句。回溯本身是指数级算法，如果 n 达到 20 以上，裸跑基本会超时。这时候先想有没有更优解法，比如动态规划；如果必须用回溯，剪枝是唯一出路。另外，递归中频繁使用切片、字符串拼接、数组拷贝等操作，也会让常数很大。我自己的习惯是：尽量只维护一个 path 列表，路径进入结果时再拷贝；选择列表尽量不要每次都新建，能通过下标范围控制就不要复制数组。

5.3 面试现场容易被追问的点

如果你在准备面试，回溯专题几乎是必问的，而且面试官很喜欢追问“为什么”。我整理了几个容易被追问的细节。

第一个是复杂度分析。组合 C(n, k) 的时间复杂度大约是 O(C(n, k) * k)，因为结果数 C(n, k)，每次收集结果还要拷贝长度为 k 的路径。全排列是 O(n!)。子集是 O(2^n)。剪枝能缩小实际搜索空间，但最坏情况下复杂度不会变。这些结论要能脱口而出。

第二个是“回溯和 DFS 有什么区别”。我的回答一般是：DFS 强调的是遍历整棵树的策略，回溯是在 DFS 的过程中加入了状态恢复，使得同一份状态能被多个分支复用。回溯的重点在于“做选择、递归、撤销选择”这个循环。

第三个是“能不能用迭代实现回溯”。可以，用栈模拟递归过程，但代码会复杂很多，面试中通常没必要。除非面试官明确追问，否则我推荐保持递归写法，因为它的表达最贴近人的思维。

另外提一句，热词里的“backtrace 栈回溯”和算法里的“backtracking”是两码事。backtrace 常见于调试器里回溯调用栈，backtracking 才是这里讨论的回溯算法。如果你在面试时不小心把两者混为一谈，可能会给面试官留下基础不扎实的印象，所以用词上要严格一点。

6. 怎么把回溯练成肌肉记忆

6.1 按题型分类刷题

学习回溯最忌讳东一榔头西一棒子。今天做一个组合题，明天做一个棋盘题，这样很难形成肌肉记忆。我建议你按照题型分类，集中刷几天。

我自己的安排是这样的：第一天做组合题，77、216、39；第二天做组合去重和分割，40、131、93；第三天做子集，78、90；第四天做排列，46、47；第五天做棋盘搜索，51、37。用不了一周，你就能基本把握不同题型的差异。

这里想强调一下，光看题解没用，一定要自己动手写。一个题目，你就算看懂了十篇题解，也不如亲手画一棵递归树加跑通代码来得实在。我在刷 77 题的时候，画了整整一页纸的树形图，标注每一层 startIndex 的变化，从那之后组合类问题再也没卡过壳。

6.2 一个值得长期保留的复盘习惯

这是一个我后来才养成的习惯，但对回溯提升特别大。每次遇到做不出来的回溯题，我会先在纸上写出三个东西：第一，递归树的根节点长什么样；第二，每一层的可选列表是什么；第三，什么时候收集结果。把这三个问题想清楚，再动手写代码。

比如做 N 皇后，根节点是第一行的每一列；每一层的可选列表是对应行的每一列，但要排除冲突位置；收集结果的时机是当递归到最后一行的下一层。想清楚了，代码只是按模板填答案而已。如果写不出来，说明你对这道题还没有理解到位，这时候再去刷题，很容易变成背模板。

这里还有一个记忆口诀，也许对你有用：“选择、递归、撤销”。无论在写哪一道回溯题，只要这个循环没乱，代码的大方向就不会错。甚至面试的时候，当你不知道下一行该写什么，先想一想“我现在要不要做选择？做完选择要不要递归？递归完要不要撤销？”这一套问题就能把你拉回正轨。

我个人练下来的感觉是，回溯其实是所有暴力搜问题里最“讲道理”的一种。它不靠灵感，靠的是把状态变化理清楚。只要多画几棵树、多踩几个坑，你很快也会发现，这一类题目不过是套路加变形的组合而已。