--- title: 回溯算法：从组合问题到数独的决策树艺术 date: "2015-02-14 22:10" tags: ["算法"] published: true --- 回溯算法（Backtracking）是递归世界里的对应机制：做出选择、深入探索、发现此路不通时，精确撤销最后一步，回到分叉点重新选择。 最近刷 LeetCode，从组合求和（39）、组合（77）、N 皇后（51），一路刷到数独（37），发现数独这道题几乎是回溯算法的试金石，它逼着你回答三个问题： 1. 决策树到底按什么分层？ 2. 递归函数该返回什么？ 3. 剪枝的边界在哪里？ 下面把这一路的理解整理一下。 ## 一、回溯的本质：一套通用的框架 无论题目怎么变，回溯算法都在做三件事： ```js function backtrack(路径, 选择列表) { if (满足结束条件) { 记录结果 return } for (选择 in 选择列表) { 做选择 // 修改状态 backtrack(路径) // 递归进入下一层 撤销选择 // 恢复状态，即"回溯" } } ``` 路径是已做出的决策集合，选择列表是当前可选项。关键在于：进入下一层前修改状态，返回后必须恢复原状。这是回溯与普通 DFS 的区别所在——普通 DFS 常常只是遍历一棵已经存在的树（比如二叉树、图），节点之间互不干扰；而回溯是在一边遍历一边**构造**这棵决策树，路径变量是一份被所有分支共享的可变状态，如果不撤销，下一个分支看到的就是被污染的现场。换句话说，回溯用"恢复现场"的动作，模拟出分支之间本该有的隔离性。 在组合问题（LeetCode 77：从 1~n 选 k 个数）中，这个框架非常清晰： ```js 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`，且同一个数字可以重复使用。 ```js 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` 是在排序之后，利用单调性提前终止整段循环，而不是等递归深入之后再发现和超了才返回。 先排序再剪枝是一个常见套路：排序把无序的选择列表变成有序序列，让"后面的选项只会更差"这个判断成立，从而把一次 `continue` 升级成一次 `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)： ```js 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. 每行 1-9 不重复 2. 每列 1-9 不重复 3. 每个 3×3 宫内 1-9 不重复 而且与 N 皇后不同，数独有预设数字，搜索空间不规则，81 个格子里哪些是决策点、哪些不是，要在运行时判断。这带来三个容易被忽略的问题：决策点在哪一层循环、递归该返回什么类型、状态是拷贝还是原地修改，下面依次展开。 ### 4.1 循环顺序即树结构 数独代码里最容易写错的是循环嵌套顺序： ```js // 正确：先遍历空格（决策点），再遍历数字（选择项） 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])`，然后继续搜索其他分支，函数本身不需要返回值。数独保证有且仅有一个解，找到后必须立即停止整棵搜索树的其余分支： ```js 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 皇后类似，数独用三个维度的判断来做约束检测： ```js 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）：每次找候选数字最少的空格优先填。 ```js 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）在回溯中的典型应用：不完备、不保证最优，但凭经验大幅减少搜索空间。数独从"能做出来"走向"跑得快"，靠的就是这类剪枝，具体的算法与启发式的区别可以参考[《启发式方法论》](./12-20-启发式方法论.md)。 ## 五、回溯算法的心法 从组合到数独，回溯算法的核心从未改变，只是状态管理的复杂度在升级： | 题目 | 决策点 | 选择列表 | 约束检测 | 解的收集 | |------|--------|----------|----------|----------| | 组合 | 第几个位置 | `start ~ n` | 无 | `res.push` | | 组合求和 | 第几个位置 | 排序后的候选数组 | 剩余目标值 `remain` | `res.push` | | N 皇后 | 第几行 | `0 ~ n-1` 列 | 列 + 对角线 Set | `res.push` | | 数独 | 哪个空格 | `1 ~ 9` | 行 + 列 + 宫 | 原地修改，`boolean` 信号 | 最终心法： 1. **决策点决定循环结构**：先定位决策点（空格/位置/行），再遍历选择项；决策点永远是外层循环，选择项永远在内层展开。 2. **状态修改与撤销必须对称**：进入递归前 push，返回后必须 pop；数独是赋值，返回后必须恢复为 `.`；Set 是 add，返回后必须 delete。 3. **返回类型取决于解的数量**：收集所有解用 `void` 加全局 `res`；只要唯一解用 `boolean` 做信号弹，一旦为真就沿调用栈原样返回，不再撤销现场。 4. **剪枝是回溯的灵魂**：没有剪枝的回溯就是暴力枚举，剪枝力度决定算法能否在可接受时间内跑完；排序后的 `break`、约束转 `Set`、MRV 优先填最紧格子，都是同一件事的不同形态——尽量早地砍掉注定失败的子树。 数独这道题把"递归树长什么样"这个抽象问题，具象化为"循环嵌套顺序"这样一行代码的选择。理解了为什么 `for (num)` 必须在 `for (r, c)` 内部，也就理解了回溯算法的树形直觉。