回溯算法：从组合问题到数独的决策树艺术

回溯算法（Backtracking）是递归世界里的对应机制：做出选择、深入探索、发现此路不通时，精确撤销最后一步，回到分叉点重新选择。

最近刷 LeetCode，从组合求和（39）、组合（77）、N 皇后（51），一路刷到数独（37），发现数独这道题几乎是回溯算法的试金石，它逼着你回答三个问题：

决策树到底按什么分层？
递归函数该返回什么？
剪枝的边界在哪里？

下面把这一路的理解整理一下。

一、回溯的本质：一套通用的框架

无论题目怎么变，回溯算法都在做三件事：

function backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录结果
        return
    }

    for (选择 in 选择列表) {
        做选择           // 修改状态
        backtrack(路径)  // 递归进入下一层
        撤销选择         // 恢复状态，即"回溯"
    }
}

路径是已做出的决策集合，选择列表是当前可选项。关键在于：进入下一层前修改状态，返回后必须恢复原状。这是回溯与普通 DFS 的区别所在——普通 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 是在排序之后，利用单调性提前终止整段循环，而不是等递归深入之后再发现和超了才返回。

先排序再剪枝是一个常见套路：排序把无序的选择列表变成有序序列，让”后面的选项只会更差”这个判断成立，从而把一次 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)：

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 做信号弹，一旦为真就沿调用栈原样返回，不再撤销现场。
剪枝是回溯的灵魂：没有剪枝的回溯就是暴力枚举，剪枝力度决定算法能否在可接受时间内跑完；排序后的 break、约束转 Set、MRV 优先填最紧格子，都是同一件事的不同形态——尽量早地砍掉注定失败的子树。

数独这道题把”递归树长什么样”这个抽象问题，具象化为”循环嵌套顺序”这样一行代码的选择。理解了为什么 for (num) 必须在 for (r, c) 内部，也就理解了回溯算法的树形直觉。