入门：DFS+撤销选择、解空间树与回溯三步
基于通用算法概念 · 核于 2026-07
速查
- 定义：回溯是在解空间树上做深度优先搜索（DFS），走到死路就撤销上一步选择回退，换别的分支继续——本质是「有组织 + 可剪枝的暴力枚举」。
- 回溯三步（核心）：①选择——在当前状态尝试一个合法分支；②递归——带着这个选择进入下一层；③撤销选择——回退后把状态恢复原样，才能正确尝试下一个分支（撤销是回溯的灵魂，漏了就错）。
- 解空间树两类型：子集树（每层「选/不选」某元素，共 2ⁿ 叶，对应子集/凑数）；排列树（每层从剩余元素里挑一个，共 n! 叶，对应全排列/N 皇后）。识别树类型 = 定模板。
- for 选择：做选择 / 递归 / 撤销选择——通用模板就这一句循环，所有回溯题都长这样，区别只在「选择列表怎么生成」「何时记录答案」「剪枝条件」。
- 剪枝（核心优化）：在递归前判断当前分支「一定无解」就直接
return不递归——排序后跳过、约束提前检查、可行性预估都能大幅压缩搜索空间。 - 与暴力枚举的关系：暴力是「先枚举所有候选 → 再过滤合法」，回溯是「边枚举边判、发现无解立刻回退」，省掉整棵无解子树——本质同复杂度阶，但常数小得多。
- 全排列/组合/子集的区别：全排列用
used数组（每个元素用一次，顺序不同算不同）；组合/子集用start索引（只往后选避免重复，顺序无关）——usedvsstart是最高频的模板分水岭。 - 回溯 vs DP：回溯求「所有解」（枚举每个方案，指数级）；DP 求「最优解/方案计数」（只关心值/数，记忆化把重复子问题压到多项式）。能 DP 就别回溯，但需要输出每个具体方案时只能回溯。
- 复杂度：解空间树节点数决定——子集类 O(2ⁿ)、排列类 O(n!)，都是指数级，N 稍大就爆炸，只能解中小规模（N 皇后 N≤20、全排列 n≤12 较现实）。
- 空间：递归栈深 = 树高 O(n)，外加维护状态用的
path/used/标记数组等 O(n)。 - 去重：含重复元素时，排序 +
i>0 && a[i]===a[i-1] && !used[i-1]跳过同层重复分支，保证结果不重。 - 进阶顺序：回溯框架与剪枝优化 → 经典回溯问题 → 参考。
一、核心思想：DFS + 撤销选择
回溯的本质，是「在一棵搜索树上做 DFS」。每个节点代表「当前已经做出的选择序列」，每条边代表「再做一次选择」，从根（空选择）到任一节点的一条路径就是一个候选解。
关键在于：DFS 走到某条分支发现「走不通」（要么约束不满足，要么已无选择可做）时，不能就此结束，而要退回上一层换个分支再试——这个「退回」就是「撤销上一步选择」。如果不撤销，当前状态会污染兄弟分支的尝试，结果全错。
// 回溯通用模板：for 选择 { 做选择; 递归; 撤销选择 }
function backtrack(状态) {
if (满足结束条件) { 记录答案; return; }
for (选择 of 选择列表) {
做选择; // 把这个选择作用到状态上（加入 path、标记 used 等）
backtrack(状态); // 带着选择递归下一层
撤销选择; // 关键：恢复状态，让下一个兄弟分支的尝试干净
}
}为什么必须撤销：backtrack 复用同一个 path/状态对象，递归返回后必须把它「还原成进入本次循环时的样子」，下一个 选择 才能在一个干净的状态上尝试。漏掉撤销，path 会一直累加，所有分支都基于「脏状态」，答案全错。这是回溯最高频的 bug。
二、解空间树：子集树与排列树
回溯题先回答一个问题：这棵搜索树长什么样？ 树的形状决定了模板的写法。
子集树（每层「选/不选」，2ⁿ 叶）
适用于「从 n 个元素里取若干个」的问题——每个元素都有「选」或「不选」两种可能，n 个元素构成一棵深度为 n 的二叉树，共 2ⁿ 个叶子。
{}
选/不选 a
/ \
{a} {}
选/不选 b 选/不选 b
/ \ / \
{a,b} {a} {b} {}典型问题：子集（求所有子集）、分割等和子集（凑目标和）、0-1 背包。模板核心是「当前位置选 a[i] / 不选 a[i]」，或等价地「从 start 开始 for 每个元素选它进 path」。
排列树（每层从剩余里挑，n! 叶）
适用于「把 n 个元素排成序列」的问题——第 1 层有 n 个选择、第 2 层 n−1 个……共 n! 个叶子。
[]
/ | \
[1] [2] [3] 第 1 层：从 {1,2,3} 选 1 个
/| /| /|
[1,2][1,3][2,1]... 第 2 层：从剩余里再选 1 个典型问题：全排列、N 皇后（每行选一列）、数字排列。模板核心是「用一个 used 数组记录哪些元素已用过，for 遍历所有未用元素」。
识别技巧：题目问「组合/子集/选若干个」→ 子集树（用 start）；题目问「排列/顺序有关/每行选一个」→ 排列树（用 used）。
三、回溯三步：选择 → 递归 → 撤销
把通用模板拆成最直观的三步，所有回溯题都按这三步思考：
选择：在当前节点，遍历所有「合法的下一步」。合法性由问题约束决定——全排列是「未用过」，组合是「下标 ≥ start」，N 皇后是「列和两条对角线都没冲突」。做选择就是把状态更新（
path.push(x)、used[i]=true、board[row][col]=Q）。递归：带着这个选择调用
backtrack(新状态)，进入下一层继续搜索。这一步会深到底，直到触发结束条件或走完所有分支。撤销选择：递归返回后，必须把第 1 步对状态的修改原样还原（
path.pop()、used[i]=false、board[row][col]='.'）。撤销后，循环的下一次迭代才能在一个干净状态上尝试别的选择。
// 以全排列为例，看三步怎么落地
function permute(nums) {
const res = [], path = [], used = Array(nums.length).fill(false);
const dfs = () => {
if (path.length === nums.length) { res.push([...path]); return; } // 结束条件
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // 跳过已用元素（合法性约束）
path.push(nums[i]); used[i] = true; // ①选择
dfs(); // ②递归
path.pop(); used[i] = false; // ③撤销（缺一不可）
}
};
dfs();
return res;
}记住一句话：「做选择和撤销选择必须成对出现，作用的状态要一一对应」——push 了就 pop、设了 true 就设回 false、画了 Q 就擦掉。
四、回溯与暴力枚举的关系
回溯和暴力枚举本质是同一类方法——都是穷举解空间树。区别在于「穷举的姿势」：
- 暴力枚举：先生成所有候选（如用 n 层嵌套循环或笛卡尔积），再一个个过滤合法的。即使某条路径早期就已注定无解，也要把它生成完才丢弃。
- 回溯：边走边判。每做一次选择立刻检查约束，一旦发现「这条分支往下一定无解」，当场
return剪掉整棵子树，不再深入。
举个例子，求 [1,2,3,4] 的子集中和为 10 的方案，暴力会先列出全部 16 个子集再算和；回溯在 path 之和刚超过 10 时就停止往后加（剪枝），剩下的子树全跳过。两者最坏复杂度同阶（都是 O(2ⁿ)），但回溯靠剪枝把常数大幅降低，实战往往快几个数量级。
所以回溯 = 有组织的枚举 + 剪枝。它的价值不在「能解暴力解不了的问题」，而在「用更聪明的方式枚举，少走冤枉路」。
五、回溯 vs 动态规划（DP）
回溯和 DP 经常被混淆，因为它们处理的都是「搜索解空间」的问题。区别在于「你想要什么」：
| 维度 | 回溯 | 动态规划（DP） |
|---|---|---|
| 目标 | 求所有具体方案（每个解都要列出） | 求最优值 / 方案计数（只要一个数） |
| 子问题 | 通常无重叠或不去重，每个方案独立枚举 | 大量重叠子问题，用记忆化/状态转移去重 |
| 复杂度 | 指数级 O(2ⁿ)/O(n!)，N 大就爆炸 | 多项式级 O(n²)/O(n·k)，N 可较大 |
| 典型题 | 全排列、N 皇后、所有组合方案、数独求解 | 最长递增子序列、背包最值、方案数、编辑距离 |
| 输出 | 一个个具体的解（路径/方案） | 一个数值（最大/最小/计数） |
核心判别：
- 只要问「有多少种方案 / 最优值是多少」→ 优先 DP（用记忆化把重复子问题压平）。
- 只要问「把所有方案都列出来 / 求一个具体的可行解（如解数独）」→ 只能回溯（DP 只给值不给方案）。
一个特例：数独求解只要一个解，但因为解的「结构」无法用简洁状态描述、子问题难重叠，仍是回溯的主场。反过来，爬楼梯方案数虽是「方案」，但只问个数、子问题高度重叠，用 DP 是 O(n)，回溯则是 O(2ⁿ)——能 DP 就别回溯。
下一步
理解了回溯的核心思想（DFS+撤销）与解空间树后，下一步把「选/递归/撤销」模板落地到全排列、组合、子集三大经典，并学会设计剪枝条件压缩搜索空间，见回溯框架与剪枝优化。