回溯算法详解

从决策树到剪枝优化，彻底掌握回溯算法的核心思想与通用框架

适用人群：正在准备算法面试、学习算法设计的开发者。建议先理解递归和深度优先搜索的基本概念。

什么是回溯算法

回溯算法（Backtracking）是一种通过枚举所有可能解来求解问题的算法。它的核心思想是把问题的解空间组织成一棵决策树，从根节点出发，深度优先地探索每条可能的路径。当发现当前路径不可能产生有效解时，立即回溯到上一个决策点，尝试其他选择。

回溯可以看作是一种聪明的暴力搜索——它系统地尝试所有可能性，但通过剪枝（Pruning）提前排除不可能的分支，避免不必要的计算。

回溯算法的三个核心概念：

路径（Path）：已经做出的选择
选择列表（Choice List）：当前可以做的选择
结束条件（Termination）：到达决策树底层，无法再做选择

以 N 皇后问题为例：路径是已经放置的皇后位置，选择列表是当前行所有可用的列，结束条件是 N 个皇后全部放置完毕。

通用框架模板

几乎所有回溯问题都可以套用以下模板：

function backtrack(路径, 选择列表) {
    if (满足结束条件) {
        收集结果;
        return;
    }
    for (选择 of 选择列表) {
        做出选择;
        backtrack(路径, 新的选择列表);
        撤销选择;  // 回溯的关键步骤
    }
}

关键点：撤销选择。回溯区别于普通递归的地方就在于"做完选择、递归处理、再撤销选择"这三个步骤。撤销选择保证了状态在回到上一层时是干净的，可以正确尝试下一个分支。

经典例题：N 皇后问题

问题描述：在 N×N 的棋盘上放置 N 个皇后，使得它们互不攻击。皇后可以攻击同一行、同一列、同一对角线上的任何棋子。返回所有合法的放置方案。

这是回溯算法最经典的例题。我们从第一行开始，逐行放置皇后。对于每一行，尝试所有列，检查当前位置是否合法；如果合法，放置皇后，递归处理下一行；如果某行没有任何列可选，回溯到上一行重试。

function solveNQueens(n) {
    const result = [];
    const board = Array(n).fill(0).map(() => '.'.repeat(n));

    function isValid(row, col) {
        for (let i = 0; i < row; i++) {
            const qCol = board[i].indexOf('Q');
            if (qCol === col) return false;  // 同列
            if (Math.abs(qCol - col) === row - i) return false;  // 同对角线
        }
        return true;
    }

    function backtrack(row) {
        if (row === n) {
            result.push([...board]);
            return;
        }
        for (let col = 0; col < n; col++) {
            if (!isValid(row, col)) continue;
            board[row] = '.'.repeat(col) + 'Q' + '.'.repeat(n-col-1);
            backtrack(row + 1);
            board[row] = '.'.repeat(n);  // 撤销选择
        }
    }

    backtrack(0);
    return result;
}

思路解析：isValid 函数只需要检查当前行上方已放置的皇后——因为我们逐行放置，下方还没有皇后。同列检查简单直接；同对角线检查利用了"两个皇后在同一对角线上时，它们的行差等于列差的绝对值"这一数学性质。

经典例题：全排列

问题描述：给定一个不含重复数字的数组，返回其所有可能的排列。

例如输入 [1,2,3]，输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

function permute(nums) {
    const result = [];
    const used = Array(nums.length).fill(false);

    function backtrack(path) {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.push(nums[i]); used[i] = true;  // 做出选择
            backtrack(path);
            path.pop(); used[i] = false;  // 撤销选择
        }
    }

    backtrack([]);
    return result;
}

这里的used数组就是选择列表的状态表示——used[i] 为 true 表示 nums[i] 已经被选入当前排列，不能再选。回溯时需要同时恢复 path 和 used。

经典例题：子集问题

问题描述：给定一个不含重复元素的整数数组，返回该数组所有可能的子集（幂集）。

例如输入 [1,2,3]，输出 [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。

function subsets(nums) {
    const result = [];

    function backtrack(start, path) {
        result.push([...path]);  // 每个节点都是一个有效子集
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }

    backtrack(0, []);
    return result;
}

与排列问题的区别：子集问题通过 start 参数控制了选择范围——只考虑当前元素之后的元素，避免产生重复子集。排列问题中 [1,2] 和 [2,1] 是不同的，但子集问题中它们是同一个子集。

剪枝优化技巧

回溯算法的效率很大程度上取决于剪枝——在搜索过程中提前排除不可能产生解的分支。好的剪枝可以将指数级的时间复杂度降低到可行范围内。

常见剪枝策略：

可行性剪枝：当前选择已经不可能满足约束条件时直接跳过。如 N 皇后中的 isValid 检查。
排序后剪枝：先对输入排序，然后利用有序性质跳过不必要的分支。如组合总和问题中，排序后如果当前和已超过目标，后面的数字更大，可以直接跳过。
去重剪枝：当输入包含重复元素时，同一层中相同元素只选第一个，跳过后续相同的。方式是先排序，然后跳过 nums[i] === nums[i-1] 的情况。
限界剪枝：当剩余路径不可能超过当前最优解时剪枝，常用于求最优解的问题。

时间复杂度分析

回溯算法的时间复杂度通常是指数级的，但具体的阶数取决于问题的解空间大小和剪枝效果：

N 皇后问题：O(N!)——每行可选列数递减
全排列：O(N!)——N 个元素的所有排列
子集问题：O(2^N)——每个元素选或不选

空间复杂度主要来自递归调用栈的深度，通常为 O(N)。

实战要点总结

套框架：先写出 backtrack 函数的三个要素——结束条件、选择列表、撤销操作
画决策树：面试时在纸上画出 2-3 层的决策树，思路瞬间清晰
先写 isValid 再递归：把约束检查独立出来，代码更清晰
注意引用传递：收集结果时记得深拷贝（[...path] 或 path.slice()），否则结果会被后续回溯修改
排序是剪枝的好朋友：很多去重和剪枝策略依赖于有序输入