回溯算法（Backtracking）通过递归枚举选择；当前选择无法满足约束时，撤销最后一次状态修改并尝试其他选择。
最近练习 LeetCode 的组合求和（39）、组合（77）、N 皇后（51）和数独（37）时，数独集中涉及三个问题：
- 决策树到底按什么分层？
- 递归函数该返回什么？
- 剪枝的边界在哪里？
回溯的通用结构
无论题目怎么变，回溯算法都在做三件事：
function backtrack(路径, 选择列表) {
if (满足结束条件) {
记录结果
return
}
for (选择 in 选择列表) {
做选择 // 修改状态
backtrack(路径) // 递归进入下一层
撤销选择 // 恢复状态，即"回溯"
}
}路径是已做出的决策集合，选择列表是当前可选项。关键在于：进入下一层前修改状态，返回后必须恢复原状。普通 DFS 通常遍历已存在的树或图；回溯在搜索过程中构造决策路径，多个分支共享同一份可变状态。若不撤销状态，下一个分支会继承上一个分支的选择。撤销操作保证各分支从相同的父状态开始。
在组合问题（LeetCode 77：从 1~n 选 k 个数）中，这个框架非常清晰：
var combine = function (n, k) {
const res = []
const track = []
function backtrack(start) {
if (track.length === k) {
res.push([...track]) // 结束：凑够了 k 个
return
}
for (let i = start; i <= n; i++) {
track.push(i) // 做选择
backtrack(i + 1) // 递归：下一层从 i+1 开始，避免重复
track.pop() // 撤销：弹出，回到上一层的状态
}
}
backtrack(1)
return res
}这里的决策点是”第几个位置填什么数”，选择列表是 start ~ n。树的每一层代表一个待填充的位置，start 参数保证了同一组合不会因为顺序不同被重复统计。
组合总和的去重与剪枝
组合求和（LeetCode 39）在组合的基础上加了一个约束：所有数字之和恰好等于目标值 target，且同一个数字可以重复使用。
var combinationSum = function (candidates, target) {
const res = []
const track = []
candidates.sort((a, b) => a - b) // 排序是剪枝的前提
function backtrack(start, remain) {
if (remain === 0) {
res.push([...track])
return
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remain) break // 剪枝：后面只会更大，直接停止本层循环
track.push(candidates[i])
backtrack(i, remain - candidates[i]) // 注意是 i 不是 i+1：允许重复选自己
track.pop()
}
}
backtrack(0, target)
return res
}这道题揭示了两种不同性质的剪枝：
- 去重剪枝：
combine里的i + 1保证不会选到自己之前的位置，避免统计出重复组合。 - 无效剪枝：
combinationSum里的candidates[i] > remain是在排序之后，利用单调性提前终止整段循环，而不是等递归深入之后再发现和超了才返回。
排序后，候选数组单调递增；当 candidates[i] > remain 时，后续候选项也无法满足剩余目标值，因此可以用 break 结束本层循环，而不是仅跳过当前分支。
N 皇后：按行选择列
N 皇后（LeetCode 51）需要在 n×n 棋盘上放置皇后。由于每行必须且只能放置一个皇后，搜索可以按行进行：
不需要在 n² 个格子里选 n 个，只需要在第 0 行选一个列，第 1 行选一个列……第 n-1 行选一个列。
路径从 track[] 变成了 track[row] = col，即”第 row 行的皇后在第 col 列”。
冲突检测也变成了数学问题：
- 同列：
col === c - 主对角线：
row - col === r - c - 副对角线：
row + col === r + c
用三个 Set 记录已占用的列和两条对角线，冲突检测压缩到 O(1)：
const cols = new Set()
const diag1 = new Set() // row - col
const diag2 = new Set() // row + col
// 做选择时
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
// 撤销时
cols.delete(col)
diag1.delete(row - col)
diag2.delete(row + col)这是回溯算法的一个经典优化方向：把约束条件转化为状态集合，避免每次线性扫描棋盘。付出的代价是额外维护三份和路径同步增减的状态，好处是把每一步的合法性检测从 O(n) 降到 O(1)。
数独的回溯实现
数独（LeetCode 37）同时包含三类约束：
- 每行 1-9 不重复
- 每列 1-9 不重复
- 每个 3×3 宫内 1-9 不重复
而且与 N 皇后不同，数独有预设数字，搜索空间不规则，81 个格子里哪些是决策点、哪些不是，要在运行时判断。这带来三个容易被忽略的问题：决策点在哪一层循环、递归该返回什么类型、状态是拷贝还是原地修改，下面依次展开。
4.1 循环顺序即树结构
数独代码里最容易写错的是循环嵌套顺序：
// 正确：先遍历空格（决策点），再遍历数字（选择项）
function solveSudoku(board) {
function backtrack() {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] !== '.') continue
for (let num = 1; num <= 9; num++) { // 选择项
const ch = String(num)
if (isValid(board, r, c, ch)) {
board[r][c] = ch
if (backtrack()) return true // 关键！
board[r][c] = '.'
}
}
return false // 1-9 全不行，回溯
}
}
return true // 没有空格了，说明填完了
}
backtrack()
}为什么不能把 for (num) 放到行列循环外面？
因为回溯树的分层依据是”决策点”，数独的决策点是空格，不是数字。每一层递归的语义是：“处理当前这个空格，选一个合法的数字填进去。”
如果把数字放外层，语义变成了：“先拿住数字 5，去所有空格找能填 5 的位置。“这会导致：
- 同一个空格被重复尝试
- 递归回来时不知道上一个处理的是哪个空格
- 回溯链条彻底断裂，因为一次递归调用不再对应”确定一个格子”这个单一职责
核心原则：决策点在哪一层，哪一层就应该是循环的最外层；选择项永远在决策点内部展开。
4.2 boolean 返回值控制搜索终止
数独的 backtrack 返回 boolean，这是与组合题最大的不同。
组合题要收集所有解，所以找到解时 res.push([...track])，然后继续搜索其他分支，函数本身不需要返回值。数独保证有且仅有一个解，找到后必须立即停止整棵搜索树的其余分支：
board[r][c] = ch // 做选择
if (backtrack()) { // 递归：问下一层"你搞定了吗？"
return true // 下一层说搞定了，我也向上汇报搞定
}
board[r][c] = '.' // 否则：撤销，试下一个数字最底层（没有空格时）返回 true。每一层收到 true 后立即 return true，从而退出所有循环和递归。此时棋盘保留最终答案，因此该路径不能执行撤销操作。
收集所有解时，回溯函数通常使用 void 返回值并遍历完整个搜索树；只需一个解时，boolean 返回值用于表示是否继续搜索。
4.3 原地修改：引用即答案
数独的 board 是二维数组，传入的是引用。board[r][c] = '5' 直接修改了原始数组。所以不需要像组合题那样把 track 拷贝进 res，最终 board 本身就是答案，函数甚至可以没有返回值意义上的”结果”，只有一个表示”是否成功”的信号。
这是回溯的另一种模式：原地修改加布尔信号，适用于”求解一个确定解”而非”收集所有解”的场景，好处是省掉了每次拷贝路径的开销。
4.4 剪枝：三个方向的集合
与 N 皇后类似，数独用三个维度的判断来做约束检测：
function isValid(board, r, c, ch) {
for (let i = 0; i < 9; i++) {
if (board[r][i] === ch) return false // 行
if (board[i][c] === ch) return false // 列
}
const boxR = Math.floor(r / 3) * 3
const boxC = Math.floor(c / 3) * 3
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[boxR + i][boxC + j] === ch) return false // 宫
}
}
return true
}这里是 O(1) 空间换来一次 O(27) 的检测，如果每个格子都提前维护行、列、宫三张”已用数字”位图（用 9 位的整数或 Set 表示），检测可以进一步降到 O(1)，但对 9×9 的固定规模而言，直接扫描已经足够快，没必要为了理论上的常数优化牺牲代码可读性。
4.5 启发式：MRV 优化
基础版是顺序扫描空格，从左到右、从上到下。进阶做法是 MRV（Minimum Remaining Values）：每次找候选数字最少的空格优先填。
var solveSudoku = function(board) {
// 检查在 (r, c) 放 num 是否合法
const isValid = (r, c, num) => {
for (let i = 0; i < 9; i++) {
if (board[r][i] === num || board[i][c] === num) return false;
}
const boxR = Math.floor(r / 3) * 3;
const boxC = Math.floor(c / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[boxR + i][boxC + j] === num) return false;
}
}
return true;
};
// 获取某个空格的所有候选数字
const getCandidates = (r, c) => {
const nums = [];
for (let i = 1; i <= 9; i++) {
if (isValid(r, c, String(i))) nums.push(String(i));
}
return nums;
};
const backtrack = () => {
let minOptions = 10;
let bestR = -1, bestC = -1, bestNums = [];
// MRV：扫描全盘，找候选数字最少的空格
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] !== '.') continue;
const nums = getCandidates(r, c);
if (nums.length < minOptions) {
minOptions = nums.length;
bestR = r;
bestC = c;
bestNums = nums;
if (minOptions === 1) break; // 唯一候选，已经最优
}
}
if (minOptions === 1) break;
}
// 没有空格了，解完
if (bestR === -1) return true;
// 只处理这个最优格子
for (const num of bestNums) {
board[bestR][bestC] = num;
if (backtrack()) return true;
board[bestR][bestC] = '.';
}
return false;
};
backtrack();
};MRV 背后的直觉是：约束越紧的格子越应该先填，因为它出错的可能性最小，而且尽早暴露矛盾——如果某个格子的候选数字是 0 个，说明当前路径已经走不通，可以立刻回溯，不用等填完其他格子再发现矛盾。这本质上是把”failure 尽早暴露”作为搜索策略，是约束满足问题（CSP）里的通用启发式，不止用在数独上。
这是启发式（Heuristic）在回溯中的典型应用：不完备、不保证最优，但凭经验大幅减少搜索空间。数独从”能做出来”走向”跑得快”，靠的就是这类剪枝，具体的算法与启发式的区别可以参考《启发式方法论》。
回溯问题中的状态管理
这些题目都按决策点展开选择，但状态与约束检测方式不同：
| 题目 | 决策点 | 选择列表 | 约束检测 | 解的收集 |
|---|---|---|---|---|
| 组合 | 第几个位置 | start ~ n | 无 | res.push |
| 组合求和 | 第几个位置 | 排序后的候选数组 | 剩余目标值 remain | res.push |
| N 皇后 | 第几行 | 0 ~ n-1 列 | 列 + 对角线 Set | res.push |
| 数独 | 哪个空格 | 1 ~ 9 | 行 + 列 + 宫 | 原地修改，boolean 信号 |
实现时需要检查以下几点：
- 决策点决定循环结构：先定位决策点（空格/位置/行），再遍历选择项；决策点永远是外层循环，选择项永远在内层展开。
- 状态修改与撤销必须对称：进入递归前 push，返回后必须 pop；数独是赋值，返回后必须恢复为
.；Set 是 add，返回后必须 delete。 - 返回类型取决于解的数量：收集所有解时使用
void和全局res；只需一个解时用boolean表示是否已找到解。返回true后直接沿调用栈返回，不再撤销当前解的状态。 - 剪枝减少无效搜索：排序后的
break、用Set记录约束、MRV 优先处理候选项较少的格子，都会更早终止无法得到解的分支。
数独中递归树的分层直接对应循环嵌套顺序：for (num) 必须位于定位空格的 for (r, c) 内部，才能保证每次递归只处理一个格子。
