企业官网建设流程全解析

回溯算法，在很多刷题场景里属于“一看就会、一写就废”的类型。全排列、组合总和、N皇后、解数独……背景五花八门，但只要抓住“不停地尝试、碰壁就回头”这条主线，所有这些题目都能用同一套模式解决。这篇文章我会把回溯算法的底层逻辑拆开讲清楚，然后带你把几个高频题目从零开始完整写一遍，不只贴答案，还把为什么这么写、哪些位置最容易出问题都说明白。不管你是刚开始刷算法题的新手，还是想系统整理回溯思路的进阶选手，都可以直接照着操作。

1. 回溯算法到底在做什么：暴力搜索的优雅外壳

1.1 从“试错”到“决策树”：一个生活化的理解方式

先别急着看代码，我从一个生活场景说起。

假设你在一个地下迷宫里找出口，每个岔路口都有好几条路。最笨的办法是什么？每条路都走一遍：走进去发现是死胡同，就退回到刚才的岔路口，换下一条路继续试。直到把所有岔路都试完，你自然知道哪条路能到终点。

回溯算法的核心就是这个过程。它把一个复杂的选择过程看成一棵不断分叉的“决策树”，每往前走一步，就对应树上的一次分支选择；碰到不满足条件的情况，就撤回上一个状态，重新选。这个“撤回来重新选”的动作，在算法里叫状态重置，也是回溯和普通递归最大的区别。

为什么要强调状态重置？我举个例子你就明白了。

假设你要在全排列中找到所有满足某个条件的排列，比如[1, 2, 3]的全排列。你先把1放在第一位，然后递归去排列剩下的2和3；排列完所有以1开头的序列之后，你需要把1从结果里拿出去，让2也有机会放在第一位。如果只顾着递归、不负责“打扫战场”，第一位的1永远留在那里，那后面的情况根本没法尝试。

这就是回溯的思想代价：它用“深度优先遍历整棵决策树”的方式，保证每一种合法可能性都被覆盖，同时用“撤销选择”保证每种状态都被完整复用。换句话说，这是一套系统化、不漏不重的暴力搜索，只是披了一层递归的外壳，所以显得比“多层for循环”优雅得多。

1.2 什么样的题目一看就是回溯的活

刷过一段时间题之后你会发现，下面这些特征一出现，基本就是在召唤回溯算法：

• 题目让你列出所有可能的“方案”“组合”“排列”“走法”，且数量是有限的。
• 你写循环时发现循环层数不确定。比如从数组里选任意个数字，循环层数是变化的——这时候就需要递归来动态控制层数。
• 题目里明显存在“选择”和“撤销选择”的交替过程。比如放了皇后要判断是否冲突，不满足就撤掉换个位置放。

我自己的判断经验是：只要题目里出现“所有可能”四个字，十有八九是回溯。像“返回所有子集”“得到所有符合条件的组合”“输出所有可行路径”，这些都是标准的回溯用例。当然，“所有可能”也可能是动态规划求方案数，但只要题目要求你具体列出每一种方案，而不是只求数量，那基本就锁定回溯了。

1.3 回溯、递归和深度优先搜索有什么关系

很多人把这三个词混着用，其实它们的关系很清晰：

• DFS（深度优先搜索）是一种遍历策略，沿着一条路走到黑，再回头换路。
• 递归是实现DFS最常见的编程手段，因为“走下一步”和“走当前步”的逻辑完全一样，天然适合函数自己调自己。
• 回溯是DFS的一种应用场景，它在DFS的基础上增加了“状态恢复”这一步。

我用一句话总结：回溯 = DFS + 状态重置。

比如下面这段最基础的DFS遍历代码，它只负责输出路径，不涉及撤销操作：

def dfs(path): if 终止条件: 输出(path) return for 每种选择 in 可选集合: path.append(选择) dfs(path)

这是纯粹的深度优先遍历。而回溯只是在递归之前做“选择”，递归之后做“撤销选择”：

def backtrack(path): if 终止条件: 输出(path) return for 每种选择 in 可选集合: path.append(选择) # 做选择 backtrack(path) path.pop() # 撤销选择

就是多了这一行撤销，遍历框架变成了搜索框架，能解决的范围瞬间从一个图扩大到了整个解空间。记住这个区别，后面所有的代码都从这个框架演化。

2. 回溯模板与核心细节：为什么我的代码老是“不对”

2.1 一个看了就能上手的通用模板

我刷回溯题前期最大的体会是：别一上来背题解，先背模板。回溯题虽然场景各不相同，但代码结构高度统一。我平时用的模板是下面这个，你直接拿来当骨架写：

def backtrack(路径, 选择列表): if 满足终止条件: 记录当前路径 return for 选择 in 选择列表: # 剪枝：排除明显不成立的分支 if 选择不合法: continue # 做选择 path.append(选择) 更新相关状态 # 进入下一层决策树 backtrack(路径, 更新后的选择列表) # 撤销选择 path.pop() 恢复相关状态

你会发现每一道回溯题只是在“终止条件”“选择列表”“合法性判断”这三个地方做文章，整体框架是不动的。

这个模板里最容易被忽略的是“更新相关状态”和“恢复相关状态”必须完全对应。你在递归前改了哪些变量，递归后就得原样改回来。写代码时我习惯把“做选择”和“撤销选择”看成一对对称操作，少了哪一个，搜索过程就失真了。

2.2 为什么“撤销选择”是灵魂操作

这一节我想认真讲一下。很多新手写的回溯代码，结果里会出现大量重复或错误答案，原因基本都是撤销操作没做好。

我拿全排列举例子。求数组[1, 2, 3]的全排列，用一个used数组记录每个数字是否已经被选中。如果递归返回后不把used[i]改回False，这个数字就被永久标记为“已使用”，那么轮到这个数字该出现在其他位置上时，它永远没有机会了。

# 错误示例：没有撤销 for i in range(n): if used[i]: continue used[i] = True # 标记使用 path.append(nums[i]) backtrack(path, used) # 少了一步 used[i] = False # 少了一步 path.pop()

你可以想象一下：第一层递归选了1，之后所有递归层都认为1被占用，后面的排列全都是从2和3里挑，最终输出的结果会变成[1,2,3]、[1,3,2]这样的少数几条，其他的排列全丢光了。

所以我建议你写回溯代码时，把这两行代码当成一个整体：

used[i] = True path.append(...) # 递归... used[i] = False path.pop()

写的时候先写撤销，再写递归，甚至先写一行注释提醒自己“这里一定要恢复状态”。养成这个习惯之后，回溯题的正确率会高非常多。

2.3 剪枝的本质：提前砍掉没希望的分支

回溯算法虽然能枚举完所有情况，但那是理想状态。如果某个分支从一开始就不可能产生合法答案，你还继续往下递归，纯粹是在浪费算力。提前判断并跳过这种分支的动作，叫剪枝。

最经典的剪枝场景是组合总和问题：给定一个候选数组和一个目标值，要求从数组中选出若干个数（可重复），使它们的和等于目标值。

如果你在某一步发现当前和已经大于目标值了，那不管后面再加什么正数，结果都只会更大，不可能等于目标值。所以这个分支可以直接停止。

if current_sum > target: return

就这一行简单的判断，能把搜索树的很大一部分直接砍掉。

剪枝的另一种形式是“提前判断剩余元素够不够”。比如你要求组合中必须包含k个元素，当前已经选了m个元素，而剩下的可选项不足k-m个，那这个分支也可以放弃。

我把剪枝理解为对未来结果的可行性判断。判断越准确，搜索效率越高。但要注意剪枝条件必须严格成立，不能为了省时间写出错误的剪枝逻辑，那会让正确答案被误杀。宁可在后期加上记忆化，也不要写出模棱两可的剪枝条件。

2.4 参数设计：哪些该放进递归函数，哪些该提取成全局

回溯函数的参数设计，决定了代码是清晰还是混乱。我总结了一套很朴素的标准：

• 会随着递归层次变化的数据，尽量作为参数传下去。比如begin（下一次选择的起始下标）、current_sum（当前路径和）、path（当前已选列表）。
• 全程共用的状态数据，可以放在外部变量里。比如候选数组、目标值这些只读数据，没必要每次递归都复制一份。
• 需要频繁修改并恢复的标记数据，我一般也放外部，比如used数组。放进参数里反而容易引起状态没恢复的混淆。

举个例子，组合总和问题里，为了避免出现[2, 3]和[3, 2]这种重复组合，我会用begin参数控制选择范围：

def backtrack(begin, current_sum, path): if current_sum == target: res.append(path[:]) return for i in range(begin, len(candidates)): # ... backtrack(i, current_sum + candidates[i], path + [candidates[i]])

begin的作用是保证每次递归只选择当前及之后的元素，这样组合不会回头重复选择已经排过的位置。很多人漏了begin，结果输出里全是顺序不同但元素相同的重复组合，还以为是去重逻辑写错了。

当你把参数设计清楚了，写任何回溯题都会顺手很多。核心原则就一条：每层递归之间互不干扰的变量才适合做参数，全局共享的状态尽量放外部。

3. 从实战出发：四个经典场景手把手拆解

3.1 组合总和：第一个必写的入门题

题目背景我直接简化一下：给定一个无重复元素的数组candidates和一个目标数target，找出所有可以使数字和等于target的组合。同一个数字可以无限重复使用。

这题特别适合当回溯入门题，因为它同时涉及到“路径记录”“当前和更新”“起始下标控制”这三个基本元素。我写一版可以直接跑的代码：

def combination_sum(candidates, target): res = [] candidates.sort() # 排序是为了剪枝更高效 def backtrack(begin, current_sum, path): if current_sum == target: res.append(path[:]) return for i in range(begin, len(candidates)): if current_sum + candidates[i] > target: break # 因为已经排序，后面的数只会更大 path.append(candidates[i]) backtrack(i, current_sum + candidates[i], path) path.pop() backtrack(0, 0, []) return res

有几个细节值得说。

第一，backtrack(i, ...)传入的起始下标还是i，不是i+1，因为题目允许重复使用同一个数字。如果你写成i+1，那就变成每个数字只能用一次了，这是题目之间最常见的差异。

第二，path.pop()必须在递归之后执行，它撤销的是“刚加入的元素”。你可以在纸上模拟一遍：走到叶子节点返回后，把最后一个元素去掉，才能往兄弟分支继续走。

第三，为什么排序之后用break而不是continue？因为数组已经升序排列，当前元素加上去已经超过目标值，后续更大的元素更不可能满足条件，直接终止整个循环层即可。如果没有排序，就只能用continue，但那样会浪费更多无效判断。

我实测下来，这个写法在普通数据规模下表现很稳定，也是面试里最容易被接受的写法。

3.2 全排列：把 used 数组用熟

全排列问题我就不多介绍题干，给你看一下核心代码：

def permute(nums): res = [] n = len(nums) used = [False] * n def backtrack(path): if len(path) == n: res.append(path[:]) return for i in range(n): if used[i]: continue used[i] = True path.append(nums[i]) backtrack(path) path.pop() used[i] = False backtrack([]) return res

全排列跟组合的核心区别在于：组合用begin控制不回头，排列用used确保每个位置都能选到所有元素。

我在学习时踩过一个有意思的坑：res.append(path[:])里的[:]是用来复制列表的。如果直接写res.append(path)，后续的path.pop()会修改同一个列表对象，导致最后保存在res里的所有结果都是空列表。这个错误极其隐蔽，运行时不报错，结果却是全错的。

后来我每次记录结果的代码都习惯性地写path[:]，相当于告诉后来的自己：这里要一份当前状态的快照，不要引用本身。这个习惯帮我避开了一整类bug。

3.3 子集问题：同一个模板的一个小变种

求一个数组的所有子集，比如[1, 2, 3]的所有子集是[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]。

它的特殊之处在于：每个元素只有选或者不选两个分支，且你不需要等到路径长度等于n才记录结果，而是每到一个节点都算一个答案。

def subsets(nums): res = [] def backtrack(begin, path): res.append(path[:]) for i in range(begin, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return res

对比组合总和，这里少了一个“等于目标值”的判断，改成了“每层都记录”。这就是我之前说的，模板的终止条件和记录时机要因题而异。

子集问题还有一个变种叫“查找所有满足条件的子集”，比如子集元素和不超过某值。做法就是在现有模板的循环里加剪枝。你掌握子集的写法后，这类变种题基本就是加一行判断的事。

3.4 N皇后：在棋盘上实践冲突检查

N皇后问题是我心中最能体现回溯之美的题：在n×n的棋盘上放n个皇后，要求任意两个皇后不能出现在同一行、同一列或同一条对角线上，返回所有可行布局。

它的核心思路其实不复杂：按行推进，每一行选择一个位置放皇后，放之前检查列和两条对角线是否冲突，冲突就换下一个位置。如果一整行都找不到合法位置，就回溯到上一行重新选。

我写一版比较直观的代码：

def solve_n_queens(n): res = [] # col[i] 表示第 i 列是否被占用 col = [False] * n # diag1 表示 r - c 这条对角线，diag2 表示 r + c 这条对角线 diag1 = [False] * (2 * n - 1) diag2 = [False] * (2 * n - 1) def backtrack(row, cur): if row == n: res.append(["." * i + "Q" + "." * (n - i - 1) for i in cur]) return for c in range(n): if col[c] or diag1[row - c + n - 1] or diag2[row + c]: continue col[c] = True diag1[row - c + n - 1] = True diag2[row + c] = True cur.append(c) backtrack(row + 1, cur) cur.pop() diag2[row + c] = False diag1[row - c + n - 1] = False col[c] = False backtrack(0, []) return res

这里用row - c和row + c表示两条对角线，是因为在同一对角线上的所有格子满足这两个值之一相同。由于row - c可能是负数，我统一加上n - 1偏移，把它映射到数组下标。这个技巧看起来不起眼，但能少写好多复杂判断。

N皇后的难点不在于“理解回溯”本身，而在于状态的设计。如果你用二维数组模拟棋盘，每一步都要遍历检查整行整列，代码会非常笨重。换成列数组加两个对角线数组，每次判断都是O(1)的复杂度，整个搜索过程轻快不少。

4. 常见问题与性能优化：这些坑你踩过几个

4.1 重复结果和顺序问题

回溯题最常见的报错就是结果集里出现重复项。比如组合总和题目里，如果你没有用begin控制起点，[2, 3]和[3, 2]会被当成两个不同结果。

我用了一个很简单的原则：组合类题目用begin控制方向，排列类题目用used控制元素。但有些题目候选数组中本身包含重复元素，比如[1, 1, 2]的子集，这时候就需要“排序 + 同层去重”。

所谓同层去重，是指在同一层循环中，如果当前元素和前一个元素相同，并且前一个元素在这个分支没有被用过，就跳过：

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

这个判断删掉的是“同层”的重复分支，而保留“不同层”的合法分支。很多人会在这里写错成if used[i - 1]之类的条件，结果把合法解法也砍掉了。我的经验是：先画一个小小的决策树，把同一层重复的情况标注出来，再决定去重条件，比凭空调代码稳得多。

4.2 无限递归和栈溢出

无限递归在回溯里并不罕见，典型原因是终止条件写得不到位。比如递归函数里你想控制选择层数，但忘记在“路径长度等于n”时返回；或者使用begin时忘了递增，导致每次进入递归时可选范围没有缩小。

我遇到过一个很典型的错误：在组合总和题里，backtrack(i, ...)写成backtrack(0, ...)，结果每次递归都从数组开头重新选，递归层数无限增加，直接爆栈。

排查这类问题有个好方法：在递归函数开头打印当前path，观察它是否在反复震荡。如果路径长度一直不下减或者一直不增加，多半是参数传递出了问题。其次检查终止条件是否放在递归函数最前面。

4.3 超时问题：优化剪枝和状态设计

回溯算法的本质是穷举，规模一大就容易超时。我从两个方向来优化。

第一个方向：优化剪枝条件。比如组合总和里，先对候选数组排序，一旦当前和超过目标就break，可以减少大量无效递归。子集和问题里，也可以先用前缀和判断“剩余元素全选上也无法满足条件”，直接剪枝。

第二个方向：优化状态存储与判断。就像N皇后用三个数组代替二维棋盘检查，很多回溯题的问题核心都在“合法性判断”这一步。如果这一步是O(n)复杂度，整个搜索时间会放大n倍；优化成O(1)后，搜索效率会明显提升。

还有一个思路是用记忆化，但这里要额外说一句：回溯本身通常就是一次性的深度搜索，结果路径各不相同，记忆化的适用场景有限。只有当问题存在大量重复子问题、并且你只需要计数而不需要列出具体路径时，记忆化才真正有优势。否则强行加记忆化，反而可能因为状态维度太多而内存爆炸。

4.4 回溯调试速查表

我把实际调试中常见的几类问题整理成一张表，方便你排查：

这张表是我自己在多次Debug中沉淀下来的，每次遇到回溯问题卡住，我都会先按这几种情况对号入座，大多数时候五分钟内就能定位问题。

5. 时间复杂度与空间复杂度：提前估算搜索规模

5.1 回溯复杂度分析的基本思路

回溯的时间复杂度不是看某一次递归的执行时间，而是看整棵搜索树有多少个节点。每个节点代表一次“做选择”的状态，节点数量决定了基本操作次数。

• 全排列：第一层有n个选择，第二层n-1个，整体约为n!级别的节点。
• 组合问题：从n个元素中选k个，节点数约等于组合数C(n, k)乘以上下层的路径长度。
• 子集问题：每个元素有选/不选两种可能，理论节点数为2^n。

这里强调一点：剪枝后的实际节点数通常远小于理论最大值。以组合总和为例，如果目标值很小，递归很快就会因为current_sum > target而返回，整棵树会瘦很多。所以分析复杂度时，我会先按最坏情况算，再结合实际条件修正。

5.2 空间复杂度要算三部分

空间复杂度很多人只算一个递归栈，其实回溯的空间消耗至少包含三块：

• 递归调用栈：最大深度等于搜索树的层数。全排列是n层，子集也是n层，所以栈深度为O(n)。
• 路径存储：path列表最长为n，占用O(n)。
• 结果集：如果题目要求返回所有结果，最终res会存储M个方案，每个方案长度可能为n，这部分空间是O(M*n)，也常被忽略。

我一般估算思路是“边做边攒”的结果集也算进空间范围，因为面试官问到空间复杂度时，往往会追问“结果集要不要算”。如果你用的是生成器方式按需返回结果，那结果集空间可以不计，但大多数递归写法都是全量返回，所以还是老实算进去比较好。

5.3 剪枝对实际性能的影响

理论上全排列是O(n!)，但实际写出来之后往往能够承受n=10左右的规模；组合总和这类题，因为剪枝非常有效，能接受的规模会更大。

我分享一个实测过的对比：在随机生成的10个不同数字里做全排列，结果是约三百多万条路径，普通Python递归跑起来已经能感到明显耗时。但你给同样的搜索过程加上“只求满足某种约束的解”之后，比如剪掉90%的分支，性能表现会有质的飞跃。

所以我的个人建议是：不要被最坏复杂度吓到，也不要忽略剪枝的威力。回溯在绝大多数学算法场景里都不是最终性能瓶颈，真正的问题是“要不要枚举所有解”。如果题目只要求最优解或方案数，你就要考虑动态规划或贪心方案，而不是硬用回溯。

6. 经验总结与进阶方向

6.1 我怎么判断一道题该用回溯

把刷过的题放在一起对比之后，我发现回溯题都有一个共同特征：题目空间是一个可枚举的决策树，且每个分支可以用相同的规则继续展开。

比如组合和排列，决策规则都是“当前选哪个元素”，下一层的选择规则和上一层完全一致。N皇后略微复杂一些，但本质上也是“当前行放哪个位置”，每层的判断逻辑相同。

当你发现一个问题可以拆成“第i步做什么选择”的时候，就可以用回溯去套。如果问题还能分成多个阶段、且每阶段的选择影响后面阶段，那回溯基本是首选方案。

6.2 回溯和动态规划的分工

很多初学者混淆回溯和动态规划，我来做一个简单的区分。

• 回溯用于枚举所有具体方案，它的输出是“一组一组的路径”。
• 动态规划用于求最优值或方案数量，它的输出往往是一个数值（最少步数、方案数、最大价值等）。

举一个例子：求从起点到终点的所有路径，用回溯；求从起点到终点的最短路径条数，用动态规划。如果题目只是问“有多少种方法”，用回溯硬枚举会非常慢，因为每一条路径都值得被记下来。这时候动态规划能利用重叠子问题大幅降低复杂度。

我把这段话记在笔记里当选择依据：题目要求列出方案，回溯；题目只让你数个数或算最优值，先想动态规划。

6.3 两个我自己很受用的实操心得

第一心得是“先画树，再写代码”。动手写回溯前，我会拿小例子在纸上画出决策树。比如全排列的n等于3时，先手动画出所有分支，然后我就清楚哪里该做选择、哪里该撤销、哪里该剪枝。很多时候代码写不出来，不是因为不会递归，而是没把决策树画明白。

第二心得是“把剪枝写在最前面”。在循环里尽量把能提前排除的情况放在处理逻辑之前。例如组合总和里，我先把候选数组排序，再在进入循环时判断“加上当前元素后是否超target”，超了就break，减少了一大堆无效递归。这个习惯让我的代码不仅更快，也更容易被别人看懂。

6.4 回溯的更广阔应用场景

回溯并不仅仅存在于算法题里。现实中很多场景都能看到它的影子：

• 搜索引擎的候选集生成：根据前缀、权重等条件逐步展开候选词，再剪掉不满足条件的分支。
• 游戏AI的走法搜索：比如棋类游戏里的“尝试一步棋，计算局面，不行就换一步”，本质上就是带评估函数的回溯。
• 排课系统与任务分配：把课程、教室、时间看成选择项，逐个尝试再检查冲突，不满足就回溯重排。
• 电路设计里的布线规划：在给定网格里寻找无冲突路径，也是典型的回溯应用。

所以掌握回溯并不只是为了应付考试，它其实是一套通用的“系统试错”思维。一旦你熟练了，很多看起来不可能手算清楚的组合问题，都可以交给程序去枚举解决。

我自己学回溯最大的体会是：不要试图背下所有题解，而是拿三四个经典题亲手画决策树、亲手调试几次状态恢复。踩过几次坑之后，你会发现自己面对新题时能很快识别出“选择什么、何时撤销、哪里剪枝”，这种手感是从博客和教程里得不到的。