回溯算法 | blog of peter

引言：为什么需要回溯

许多算法问题不是「求一个最优值」，而是「把所有符合条件的方案枚举出来」，或者「在庞大的状态空间里找一个可行解」。前者如「列出数组的所有全排列」「把字符串切成若干回文子串的所有切法」，后者如「在 $9 \times 9$ 棋盘上填出一个合法数独」「在字符网格里搜出某个单词」。

这类问题的共同特点是：解空间结构上是一棵巨大的「决策树」，每个节点代表「到目前为止已经做出的一连串选择」，每条从根到叶的路径代表一个候选解。树的规模往往是指数级甚至阶乘级的——比如 8 皇后的搜索树理论上节点数超过 $8^8$ ，数独的格子组合更是天文数字。我们不可能把整棵树显式建出来再遍历，于是需要一个能在「构造节点的过程中」边走边判断、走错了就退回来重试的机制。

这个机制就是回溯（Backtracking）。它本质上是在一棵「隐式」的搜索树上做深度优先遍历（DFS），并配合两个关键动作：剪枝（提前砍掉明显无望的子树）和撤销选择（在共享的可变状态上把上一步的修改还原，以便尝试兄弟分支）。

回溯是暴力搜索的「工程化封装」：它不改变最坏复杂度，但通过剪枝把常数和实际触发规模压到可接受的范围。掌握回溯等于掌握了一套通用的搜索问题求解范式——排列、组合、子集、棋盘、迷宫、分割、配括号、解数独……绝大多数「枚举/搜索」类题目都能套进同一个模板。

核心思想：在隐式决策树上做 DFS

决策树的视角

回溯问题的第一步，是把题目翻译成一棵「决策树」。每个节点对应「当前已经做出的部分选择」，从节点出发的每一条边对应「下一步可选的一种选择」。树的叶子（或满足结束条件的节点）就是完整解。

以「[1, 2, 3] 的全排列」为例，决策树长这样：

                []                 (根：空路径)
          /      |      \
       [1]      [2]      [3]
      /   \    /   \    /   \
  [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
    |     |     |     |     |     |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

每个内部节点处，我们枚举「还能用哪些数字」作为下一步选择；走到路径长度等于 3 的叶子时，收集一个答案。整棵树恰好有 $3! = 6$ 个叶子，对应 6 个全排列。

回溯的过程就是「先深」地走这棵树：从根出发，沿一条路一直走到叶子（记录答案），然后退回上一层，换一条没走过的边继续走。这就是 DFS 的天然形态。

为什么需要「撤销选择」

回溯有一个让初学者反复踩坑的细节：状态是共享的、可变的。我们通常用一个 path（或 board、nums）变量在递归过程中承载「当前路径」，而不是每次递归都拷贝一份新数组——拷贝会让时间常数和内存占用翻几倍。

既然状态是共享的，那么当一条路走完、要回退去尝试兄弟分支时，就必须把「当前这一步造成的影响」抹掉，否则它会污染兄弟分支的搜索。这就是「撤销选择」的来历。

整个回溯函数因此呈现一种高度对称的三段式结构：

1
2
3

做选择        // 修改共享状态（push_back / swap / 置位）
backtrack(...)  // 递归进入下一层
撤销选择      // 还原共享状态（pop_back / swap 回去 / 复位）

「做选择」与「撤销选择」必须严格成对，且作用于同一个元素。漏掉撤销、撤销错对象、在错误的层级撤销，是回溯代码最常见的 bug，后文「常见陷阱」一节会专门展开。

剪枝：砍掉无望的子树

裸的 DFS 在最坏情况下要遍历整棵决策树，规模是指数级。剪枝（Pruning）的核心思想是：在进入一个子树之前，就判断它是否可能产生合法解，若不可能则直接跳过，不再展开。

剪枝分两大类：

可行性剪枝：当前路径已经违反约束，子树里不可能有解。例如 N 皇后里某列已有皇后，则这一列的所有后续尝试都不必展开。
最优性/界限剪枝：即便有解，也已被已知更优解淘汰。例如求最短路径时，当前累计步数已超过当前最优，则剪掉。

剪枝不改变最坏复杂度（最坏情况下还是没得剪），但能极大压低实际运行时间。一个剪枝到位的回溯，常常比朴素版本快几个数量级。后文会用「组合总和」「子集 II」等例子具体展示。

通用回溯模板

几乎所有回溯题都能套进下面这个模板。模板的核心是 backtrack 函数的三要素：结束条件、选择列表、做选择 / 撤销选择。

#include <vector>

// 通用回溯模板（伪代码风格的骨架）
void backtrack(/* 路径状态 path, 选择列表, 结果集 result */) {
    if (/* 满足结束条件 */) {
        // 收集答案：有时在叶子收集（排列/组合），有时在每个节点收集（子集）
        // result.push_back(path);
        return;
    }
    for (/* 每一个合法选择 choice */) {
        if (/* 剪枝条件：该选择无望 */) continue;   // 剪枝
        做选择;          // 修改 path / 置位 used 等
        backtrack(/* 更新后的 path 与选择列表 */);
        撤销选择;        // 还原 path / 复位 used 等
    }
}

把模板具体化，最常见的几种参数形态是：

// 形态 A：用 start 控制选择起点（组合 / 子集类，顺序无关）
void backtrack(const std::vector<int>& nums, int start,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result);

// 形态 B：用 used[] 标记已用元素（排列类，顺序有关）
void backtrack(const std::vector<int>& nums, std::vector<bool>& used,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result);

// 形态 C：带额外约束参数（棋盘 / 网格类，逐行或逐格推进）
void backtrack(std::vector<std::string>& board, int row /* 或 x,y */);

记住一个判断口径：顺序是否敏感决定用 start 还是 used。若 [1,2] 与 [2,1] 视为不同（排列），用 used[] 在每层从 0 枚举；若视为相同（组合、子集），用 start 保证后续只往后选，天然避免重复。

下面按「排列 → 子集 → 组合」的顺序，逐个吃透三大类问题。

三大类问题之一：排列

示例：全排列

这是回溯最经典的入门题。给定一个不含重复数字的数组，返回其所有全排列。

#include <vector>

void backtrack(std::vector<int>& nums, int start,
               std::vector<std::vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        std::swap(nums[start], nums[i]);
        backtrack(nums, start + 1, result);
        std::swap(nums[start], nums[i]);  // 回溯
    }
}

std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    backtrack(nums, 0, result);
    return result;
}

思路解读。这里用的是「交换法」（也叫 Heap 算法的近亲），而不是上面模板里的 used[] 法。它的巧妙之处在于：把 nums 本身当作「当前路径」，通过 swap 把「已选元素」换到数组前段、start 指向前段末尾的下一个空位。第 start 位依次尝试放 nums[start..n-1] 中的每一个（与自身交换也算一种），递归进入下一层，回来后再 swap 还原。

做选择：swap(nums[start], nums[i])，把第 i 个候选换到 start 位置。
撤销选择：再 swap 一次，把数组还原成进入本层时的样子，保证兄弟分支（i+1）看到的状态干净。
结束条件：start == nums.size()，说明前 n 位都已固定，收集一份 nums 作为答案。

为什么交换法正确。关键不变式是：进入第 start 层时，nums[0..start-1] 是已确定的前缀，nums[start..n-1] 是剩余可用元素。循环把每个剩余元素轮流换到 start 位，等价于「在第 start 位枚举所有可选元素」，于是递归树恰好覆盖所有排列且不重不漏。

复杂度。时间 $O(n \cdot n!)$ ：共 $n!$ 个叶子，每个叶子拷贝一份长度 $n$ 的数组。空间 $O(n)$ 递归栈（不计结果集）。

变种一：used[] 写法。交换法省空间但稍绕，更直观的写法是用 used 数组显式标记：

#include <vector>

void backtrack(const std::vector<int>& nums, std::vector<bool>& used,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    if (path.size() == nums.size()) {           // 路径填满即一个排列
        result.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (used[i]) continue;                  // 已用，跳过
        used[i] = true;                         // 做选择
        path.push_back(nums[i]);
        backtrack(nums, used, path, result);
        path.pop_back();                        // 撤销选择
        used[i] = false;
    }
}

std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    std::vector<bool> used(nums.size(), false);
    backtrack(nums, used, path, result);
    return result;
}

两种写法等价，used[] 版更贴近通用模板，适合作为后续处理「含重复元素」的基线。

变种二：含重复元素的全排列 II。当 nums 含重复数字时，朴素回溯会产生重复排列（如 [1,1,2] 会让两个 1 互换得到相同结果）。剪枝套路是：先排序，然后在循环里跳过「与前一个相同、且前一个同层未被使用」的分支。

#include <vector>
#include <algorithm>

void backtrack(const std::vector<int>& nums, std::vector<bool>& used,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (used[i]) continue;
        // 去重剪枝：相同元素中，只允许「第一个未用的」继续，
        // 即必须保证 nums[i-1] 已被同层之前的分支用过。
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, used, path, result);
        path.pop_back();
        used[i] = false;
    }
}

std::vector<std::vector<int>> permuteUnique(std::vector<int> nums) {
    std::sort(nums.begin(), nums.end());        // 去重前提：先排序
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    std::vector<bool> used(nums.size(), false);
    backtrack(nums, used, path, result);
    return result;
}

去重条件为什么是 !used[i-1]。这是回溯去重最容易写错的地方。同一层里，对于一段连续相同的元素 nums[i-1] == nums[i]，我们只允许「按从左到右的顺序选取第一个」：若 nums[i-1] 在本层还没被用过（!used[i-1]），说明它已经被选过又被撤销了（或者根本没选），此时再选 nums[i] 就会和「之前选 nums[i-1] 的那条分支」产生重复，必须跳过。写成 used[i-1] 也能去重但效率略低（会展开更多无用分支后才发现重复），社区惯例用 !used[i-1]。

三大类问题之二：子集

示例：子集生成

给定不含重复元素的数组，返回其所有子集（幂集）。

#include <vector>

void backtrack(const std::vector<int>& nums, int start,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    result.push_back(path);  // 每个节点都是一个子集
    
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.pop_back();  // 回溯
    }
}

std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    backtrack(nums, 0, path, result);
    return result;
}

思路解读。子集问题与排列最大的区别在于收集答案的时机：排列只在叶子（路径填满）收集，而子集在每个节点都收集——因为「走到任意中间状态」本身就是一个合法子集。注意 result.push_back(path) 在函数最开头、循环之前，这样空集 []（根节点）也会被收集。

第二个区别是用 start 而非 used。子集与顺序无关（[1,2] 和 [2,1] 是同一个子集），所以用 start 限制「只往后选」，天然避免产生同一子集的多个排列。

做选择 / 撤销选择：push_back 与 pop_back 成对，作用于 nums[i]。

复杂度。共 $2^n$ 个子集，每个平均长度 $n/2$ ，时间 $O(n \cdot 2^n)$ ，空间 $O(n)$ 递归栈。

变种一：含重复元素的子集 II。和全排列 II 一样，先排序再去重，但去重条件改为「同层跳过与前一个相同者」：

#include <vector>
#include <algorithm>

void backtrack(const std::vector<int>& nums, int start,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    result.push_back(path);
    for (int i = start; i < (int)nums.size(); ++i) {
        // 同层去重：i > start 保证只在「本层」跳过，不影响纵向递归
        if (i > start && nums[i] == nums[i - 1]) continue;
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.pop_back();
    }
}

std::vector<std::vector<int>> subsetsWithDup(std::vector<int> nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    backtrack(nums, 0, path, result);
    return result;
}

i > start 与 !used[i-1] 的区别。子集用 start 控制选择，没有 used 数组，因此去重条件写成 i > start && nums[i] == nums[i-1]：i > start 表示这是本层枚举的「第二个及以后」的元素，若它与前一个相同，说明前一个同层分支已经覆盖了选它的所有子集，跳过即可。纵向递归（进入下一层时 start 变成 i+1）不受影响，因为那时 i == start，条件不触发。

变种二：位运算法求幂集。当元素无重复且 $n$ 较小（一般 $n \le 20$ ）时，可以用一个 $n$ 位整数的每一位表示「选/不选」，直接枚举 $0 \sim 2^n-1$ ：

#include <vector>

std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<std::vector<int>> result;
    for (int mask = 0; mask < (1 << n); ++mask) {
        std::vector<int> path;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i)) path.push_back(nums[i]);
        result.push_back(path);
    }
    return result;
}

位运算法不是回溯，但它揭示了子集问题的本质：每个元素「选/不选」的二叉决策，决策树是一棵深度为 $n$ 的满二叉树。回溯写法等价于对这棵二叉树做 DFS。

三大类问题之三：组合与组合总和

示例：组合总和（无限选取）

给定无重复元素的正整数数组 candidates 和目标 target，找出所有使数字和等于 target 的组合。同一个数字可以无限次选取。

#include <vector>
#include <algorithm>

void backtrack(const std::vector<int>& candidates, int start,
               int target, std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    if (target == 0) {                  // 凑满
        result.push_back(path);
        return;
    }
    for (int i = start; i < (int)candidates.size(); ++i) {
        // 剪枝：当前数已超过剩余目标，后面更大的数更不可能（前提是已排序）
        if (candidates[i] > target) break;
        path.push_back(candidates[i]);
        // 注意：可重复选取，所以下一层仍从 i 开始，而非 i+1
        backtrack(candidates, i, target - candidates[i], path, result);
        path.pop_back();
    }
}

std::vector<std::vector<int>> combinationSum(std::vector<int> candidates, int target) {
    std::sort(candidates.begin(), candidates.end());   // 排序是剪枝的前提
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    backtrack(candidates, 0, target, path, result);
    return result;
}

思路解读。这是组合类问题的典型形态：

结束条件改成 target == 0（凑满）——注意这里不再用路径长度判断，而是用「剩余目标」是否归零。
start 控制去重：因为 [2,3] 和 [3,2] 是同一组合，用 start 保证只往后选。
可重复选取体现在递归调用 backtrack(candidates, i, ...) 传的是 i 而非 i+1，允许下一层继续选同一个数。若是「每个数只能用一次」的组合总和 II，则传 i+1。
剪枝是本题的精髓：排序后，一旦 candidates[i] > target，由于后续更大，整条分支都不可能凑出，直接 break（不是 continue，因为后面只会更大）。这一剪枝把大量无用分支砍掉，是「组合总和」系列从 TLE 到 AC 的关键。

复杂度。最坏情况难以精确界界（取决于候选数与目标），粗略上界是 $O(n^{\text{target}/\min})$ 级别，剪枝后实际远小于此。空间 $O(\text{target}/\min)$ 递归深度。

变种：组合总和 II（每个数只用一次，含重复）。把 i 改成 i+1，并加上子集 II 式的同层去重：

#include <vector>
#include <algorithm>

void backtrack(const std::vector<int>& candidates, int start,
               int target, std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = start; i < (int)candidates.size(); ++i) {
        if (candidates[i] > target) break;
        if (i > start && candidates[i] == candidates[i - 1]) continue;  // 同层去重
        path.push_back(candidates[i]);
        backtrack(candidates, i + 1, target - candidates[i], path, result);  // i+1：不重复用
        path.pop_back();
    }
}

std::vector<std::vector<int>> combinationSum2(std::vector<int> candidates, int target) {
    std::sort(candidates.begin(), candidates.end());
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    backtrack(candidates, 0, target, path, result);
    return result;
}

变种：组合总和 III（ $1 \sim 9$ 选 $k$ 个凑 $n$ ）。元素集合固定为 1..9，限制选恰好 k 个，结束条件变成 path.size() == k && target == 0，是「组合」与「定长」的混合。

三大类剪枝对照

把三类问题的剪枝要点放在一起对比，便于记忆：

问题类型	选择起点	收集时机	典型去重/剪枝
排列	每层从 0 枚举 + `used[]`	叶子（`path.size()==n`）	`i>0 && nums[i]==nums[i-1] && !used[i-1]`
组合	`start` 起，传 `i` 或 `i+1`	叶子（满足和/长度）	排序 + `candidates[i] > target` 直接 `break`
子集	`start` 起，传 `i+1`	每个节点	`i > start && nums[i]==nums[i-1]`

一个口诀：排列管「用过没用」，组合子集管「往后不往前」。

经典问题详解：N 皇后

示例：N 皇后问题

在 $n \times n$ 棋盘上放置 $n$ 个皇后，使任意两个不同行、不同列、不同对角线。返回所有合法摆法。

#include <vector>
#include <string>

class Solution {
    std::vector<std::vector<std::string>> result;
    
    bool isValid(std::vector<std::string>& board, 
                 int row, int col) {
        int n = board.size();
        // 检查列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; 
             i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; 
             i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    
    void backtrack(std::vector<std::string>& board, int row) {
        if (row == board.size()) {
            result.push_back(board);
            return;
        }
        
        int n = board[row].size();
        for (int col = 0; col < n; col++) {
            if (!isValid(board, row, col)) continue;
            
            board[row][col] = 'Q';
            backtrack(board, row + 1);
            board[row][col] = '.';  // 撤销选择
        }
    }
    
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::string> board(n, std::string(n, '.'));
        backtrack(board, 0);
        return result;
    }
};

思路解读。N 皇后是「逐行决策」的典范：每一行恰好放一个皇后，因此决策树的第 row 层就是「第 row 行的皇后放在哪一列」。这把一个二维问题降成了一维枚举。

结束条件：row == n，所有行都放好了，收集当前棋盘。
选择列表：第 row 行的 0..n-1 列。
可行性剪枝：isValid 在放之前检查「列冲突 + 两条对角线冲突」，不合法直接 continue，整棵子树被砍掉。
做选择 / 撤销选择：board[row][col] = 'Q' 与 = '.' 成对。

为什么 isValid 只查上方。因为我们按行从上到下放，当前 row 下方的行还没放皇后，不可能产生冲突；同行的其他列也不会有（每行只放一个）。所以只需查「上方同列」「左上对角」「右上对角」三个方向。这是一个利用「放置顺序」省掉一半检查的典型优化。

复杂度。最坏 $O(n!)$ （第一行 $n$ 种、第二行至多 $n-1$ 种……），剪枝后实际远小。空间 $O(n)$ 递归栈 + $O(n^2)$ 棋盘。

优化一：用集合/数组替代线性扫描。isValid 每次都循环检查列和对角线，单次 $O(n)$ 。可以用三个布尔数组（或 unordered_set）维护「哪些列、哪些主对角线、哪些副对角线已被占用」，把检查降到 $O(1)$ 。对角线的关键是下标公式：主对角线 row - col 相同，副对角线 row + col 相同。

#include <vector>
#include <string>
#include <unordered_set>

class Solution {
    std::vector<std::vector<std::string>> result;
    std::unordered_set<int> cols, diag1, diag2;  // 列、主对角、副对角

    void backtrack(std::vector<std::string>& board, int row) {
        int n = board.size();
        if (row == n) { result.push_back(board); return; }
        for (int col = 0; col < n; ++col) {
            int d1 = row - col, d2 = row + col;
            if (cols.count(col) || diag1.count(d1) || diag2.count(d2)) continue;
            // 做选择
            cols.insert(col); diag1.insert(d1); diag2.insert(d2);
            board[row][col] = 'Q';
            backtrack(board, row + 1);
            // 撤销选择
            board[row][col] = '.';
            cols.erase(col); diag1.erase(d1); diag2.erase(d2);
        }
    }
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::string> board(n, std::string(n, '.'));
        backtrack(board, 0);
        return result;
    }
};

优化二：位运算加速。当 $n \le 32$ 时，可以用三个整数的位表示「列、主对角、副对角」的占用情况，利用位运算 $O(1)$ 求出本行所有可用列，并一次性枚举。这是竞赛中 N 皇后的标准写法，常数极小：

#include <vector>
#include <string>

class Solution {
    std::vector<std::vector<std::string>> result;
    int n;

    void backtrack(int row, int cols, int diag1, int diag2,
                   std::vector<std::string>& board) {
        if (row == n) { result.push_back(board); return; }
        // 本行可用列：~(cols | diag1 | diag2) 低 n 位为 1 的位
        int avail = (~(cols | diag1 | diag2)) & ((1 << n) - 1);
        while (avail) {
            int pick = avail & (-avail);     // 取最低位的 1
            avail ^= pick;                    // 清掉该位
            int col = __builtin_ctz(pick);    // 该位对应的列号
            board[row][col] = 'Q';
            // 下一行：列占用加上 pick；主对角左移（row-col 不变需左移）；
            // 副对角右移（row+col 变化需右移）
            backtrack(row + 1, cols | pick, (diag1 | pick) << 1,
                      (diag2 | pick) >> 1, board);
            board[row][col] = '.';            // 撤销
        }
    }
public:
    std::vector<std::vector<std::string>> solveNQueens(int n_) {
        n = n_;
        std::vector<std::string> board(n, std::string(n, '.'));
        backtrack(0, 0, 0, 0, board);
        return result;
    }
};

位运算版本里，「做选择」是 cols | pick，「撤销」其实由函数返回后 avail 仍保留原值天然完成——这是位运算回溯的精妙之处：状态以值传递，无需显式还原。对角线的移位方向是难点：主对角线 row - col 在 row+1 时需 col 不变则差 +1，等价于占用位左移；副对角线 row + col 差 -1，等价于右移。

经典问题详解：解数独

示例：解数独

给定一个 $9 \times 9$ 的数独棋盘（空格用 '.' 表示），填充空格使每行、每列、每个 $3 \times 3$ 宫的数字 $1 \sim 9$ 各出现一次。

#include <vector>
#include <string>

class Solution {
    // row/col/box 三个二维数组分别标记某行/某列/某宫是否已用某数字
    int rows[9][10] = {0}, cols[9][10] = {0}, boxes[9][10] = {0};

    int boxIndex(int r, int c) { return (r / 3) * 3 + c / 3; }

    bool backtrack(std::vector<std::vector<char>>& board) {
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] != '.') continue;       // 跳过已填格子
                int b = boxIndex(r, c);
                for (char ch = '1'; ch <= '9'; ++ch) {
                    int d = ch - '0';
                    if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;  // 冲突剪枝
                    // 做选择
                    board[r][c] = ch;
                    rows[r][d] = cols[c][d] = boxes[b][d] = 1;
                    if (backtrack(board)) return true;   // 找到一个解即可返回
                    // 撤销选择
                    board[r][c] = '.';
                    rows[r][d] = cols[c][d] = boxes[b][d] = 0;
                }
                return false;   // 1~9 都试过都不行，本格无解，回溯
            }
        }
        return true;            // 没有空格了，成功
    }
public:
    void solveSudoku(std::vector<std::vector<char>>& board) {
        // 预处理：把初始棋盘的占用登记进三个数组
        for (int r = 0; r < 9; ++r)
            for (int c = 0; c < 9; ++c)
                if (board[r][c] != '.') {
                    int d = board[r][c] - '0';
                    rows[r][d] = cols[c][d] = boxes[boxIndex(r, c)][d] = 1;
                }
        backtrack(board);
    }
};

思路解读。数独是「逐格决策」的回溯，与 N 皇后的「逐行」不同。外层双重循环找到第一个空格，在那里枚举 $1 \sim 9$ ，对每个候选做冲突剪枝（行/列/宫都不能有重复），合法则填入并递归。

结束条件：整张棋盘没有空格（循环走完没 return false），返回 true。
回溯触发：某空格 $1 \sim 9$ 全部试过都失败，return false 让上层换数。
早返回优化：数独只需「一个解」，所以 if (backtrack(...)) return true 一旦下层成功就立即向上传播，不再尝试其它候选——这是「求一个解」与「求所有解」的关键区别。
冲突检查 $O(1)$ ：用三个 int[9][10] 数组预登记占用，避免每次循环扫描行列宫。宫的下标公式 (r/3)*3 + c/3。

做选择 / 撤销选择：board[r][c] = ch 配合三个数组置 1，撤销时置 0。注意撤销必须紧跟在递归调用之后、且只在「该候选失败」时执行（成功路径直接 return true 跳出，无需撤销——反正不再用了）。

复杂度。最坏指数级，但数独的有效约束极强（每填一格平均候选很少），配合剪枝实际很快。工程上标准 $9 \times 9$ 数独基本瞬间出解。

优化：候选最少优先（MRV 启发式）。朴素版本按行列顺序找第一个空格，但更好的策略是每次选「候选数最少」的空格先填。这能把搜索树的分支因子压到最小，是约束满足问题（CSP）的通用启发式。实现上每层扫一遍棋盘找候选最少的空格，常数变大但分支数显著减小，总体常更优。

经典问题详解：单词搜索

示例：单词搜索

在 $m \times n$ 的字符网格中，判断给定单词 word 是否存在。单词由相邻格子（上下左右）的字符按顺序连接而成，同一格子不能重复使用。

#include <vector>
#include <string>

class Solution {
    int m, n;
    const int dx[4] = {0, 0, 1, -1};
    const int dy[4] = {1, -1, 0, 0};

    bool backtrack(std::vector<std::vector<char>>& board,
                   const std::string& word, int x, int y, int k) {
        if (k == (int)word.size()) return true;        // 全部匹配
        if (x < 0 || x >= m || y < 0 || y >= n) return false;
        if (board[x][y] != word[k]) return false;      // 字符不匹配，剪枝

        char tmp = board[x][y];
        board[x][y] = '#';                             // 做选择：标记已访问
        for (int i = 0; i < 4; ++i) {
            if (backtrack(board, word, x + dx[i], y + dy[i], k + 1))
                return true;
        }
        board[x][y] = tmp;                             // 撤销选择：恢复字符
        return false;
    }
public:
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        m = board.size(); n = board[0].size();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (backtrack(board, word, i, j, 0))
                    return true;
        return false;
    }
};

思路解读。单词搜索是「网格 DFS + 回溯」的样板：外层枚举每个格子作为起点，backtrack(x, y, k) 表示「从 (x,y) 出发，匹配 word[k..] 是否成功」。

结束条件：k == word.size()，所有字符匹配完。
剪枝：越界或字符不匹配立即返回 false。
做选择 / 撤销选择：用「把格子改成 '#'」标记已访问，避免重复使用同一格子；回溯时恢复原字符。这种「就地修改 + 还原」省去了额外 visited 数组，是网格回溯的常用技巧。
早返回：和数独一样只求一个解，四个方向任一成功即返回。

复杂度。最坏 $O(m \cdot n \cdot 3^L)$ ，其中 $L$ 是单词长度：每个起点出发，除第一步有 4 个方向外，后续每步至多 3 个方向（不能回头到刚来的格子，因为已标记）。

优化一：反向单词。若 word 的前缀在网格中很常见而后缀罕见（比如 word = "ABCCCCCC"），正向搜索会展开大量无用分支。可以统计 word 与网格的字符频率，若 word[0] 在网格出现次数多于 word.back()，则把 word 反转再搜，分支因子显著降低。这是个常数优化但效果惊人。

优化二：Trie + 多词搜索。当要搜多个单词（单词搜索 II）时，朴素地对每个单词跑一遍会重复扫网格。把所有单词建成一棵 Trie，从每个格子出发做一次 DFS，沿 Trie 同步下降，命中单词节点就记录。这样网格只扫一遍，是回溯与数据结构结合的范例。

经典问题详解：分割回文串

示例：分割回文串

给定字符串 s，把它分割成若干子串，使每个子串都是回文。返回所有分割方案。

#include <vector>
#include <string>

class Solution {
    std::vector<std::vector<std::string>> result;
    std::vector<std::string> path;

    bool isPalindrome(const std::string& s, int l, int r) {
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }

    void backtrack(const std::string& s, int start) {
        if (start == (int)s.size()) {           // 切到末尾，收集一种方案
            result.push_back(path);
            return;
        }
        for (int end = start; end < (int)s.size(); ++end) {
            if (!isPalindrome(s, start, end)) continue;   // 剪枝：非回文子串不切
            path.push_back(s.substr(start, end - start + 1));  // 做选择：切下一段
            backtrack(s, end + 1);                           // 递归切剩余部分
            path.pop_back();                                 // 撤销选择
        }
    }
public:
    std::vector<std::vector<std::string>> partition(std::string s) {
        backtrack(s, 0);
        return result;
    }
};

思路解读。分割问题是回溯里一个重要的子类：决策点是「在哪里下刀」。第 start 层决定「从 start 开始切多长的一段」，枚举 end 从 start 到末尾，若 s[start..end] 是回文则切下并递归处理 end+1 之后。

结束条件：start == s.size()，整串切完，收集 path。
剪枝：isPalindrome 不通过的 end 直接跳过，不展开子树。
做选择 / 撤销选择：push_back 一个子串 / pop_back。

复杂度。最坏 $O(n \cdot 2^n)$ ： $n-1$ 个间隙每个都可切或不切，共 $2^{n-1}$ 种分割，每段回文检查 $O(n)$ 。

优化：预计算回文表。isPalindrome 每次线性扫描，总开销大。可以先用区间 DP 预处理一个二维表 pal[i][j] 表示 s[i..j] 是否回文，递归中 $O(1)$ 查询：

#include <vector>
#include <string>

class Solution {
    std::vector<std::vector<bool>> pal;     // pal[i][j]：s[i..j] 是否回文
    std::vector<std::vector<std::string>> result;
    std::vector<std::string> path;

    void backtrack(const std::string& s, int start) {
        if (start == (int)s.size()) { result.push_back(path); return; }
        for (int end = start; end < (int)s.size(); ++end) {
            if (!pal[start][end]) continue;          // O(1) 查询
            path.push_back(s.substr(start, end - start + 1));
            backtrack(s, end + 1);
            path.pop_back();
        }
    }
public:
    std::vector<std::vector<std::string>> partition(std::string s) {
        int n = s.size();
        pal.assign(n, std::vector<bool>(n, false));
        // 区间 DP：长度从小到大
        for (int i = 0; i < n; ++i) pal[i][i] = true;            // 单字符
        for (int i = 0; i + 1 < n; ++i) pal[i][i + 1] = (s[i] == s[i + 1]);
        for (int len = 3; len <= n; ++len)
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                pal[i][j] = (s[i] == s[j] && pal[i + 1][j - 1]);
            }
        backtrack(s, 0);
        return result;
    }
};

这种「回溯 + 预处理表」是常见组合：把可枚举的子信息（如子串是否回文、两点是否连通）预先算好，回溯时只做 $O(1)$ 判断，把常数从递归里挪到预处理里。

剪枝艺术：策略汇总

回溯的「水平」很大程度上体现在剪枝上。把前面散见的剪枝手法汇总：

1. 可行性剪枝。当前路径已违反约束，整棵子树无解，立即剪。N 皇后的 isValid、单词搜索的字符比对、分割回文串的 isPalindrome 都属此类。这是最基础也最有效的剪枝。

2. 顺序剪枝（去重）。通过排序 + 同层跳过相同元素，避免产生重复方案。全排列 II、子集 II、组合总和 II 都依赖它。核心是「相同元素固定按从左到右的顺序选取」。

3. 界限剪枝。当前累计量已超出/不可能达到目标，剪掉。组合总和里 candidates[i] > target 直接 break 是典型——排序保证了「后面更大」，所以 break 而非 continue。

4. 剩余量剪枝。若剩余可选元素不足以凑满所需数量，提前终止。比如组合总和 III 选恰好 k 个，若 path.size() + (n - start) < k 则连数量都不够，直接 return。

5. 最优性剪枝（求最优解时）。当前路径的代价已不优于已知最优解，剪掉。常配合一个全局 best 变量，在分支限界中更常见，回溯里也偶有应用。

6. 对称性剪枝。利用问题对称性只搜一半。N 皇后里第一行只搜前半列，后半列是前半列的镜像解，可对半剪。

7. 启发式排序（MRV）。不改变正确性，但改变分支展开顺序，优先展开「候选最少」的分支，让失败尽早暴露。数独的「候选最少格优先」即此。

一个通用原则：剪枝越早越好。在更靠近根的位置剪掉一棵子树，省下的是整棵子树的代价。所以可行性检查应尽量在「做选择之前」做，而不是「递归进去发现不行再退」。

与动态规划的关系：记忆化回溯

回溯与动态规划（DP）并非对立，而是同一枚硬币的两面。回溯是「自顶向下」地搜索解空间，DP 是「自底向上」地填表。当回溯的搜索树里存在大量重叠子问题时，给回溯加一层「记忆化」（缓存已算过的子问题结果），就得到了记忆化搜索——它本质就是自顶向下的 DP。

何时该把回溯升级为记忆化

判断标准是：子问题是否被重复求解。

排列、组合、子集、N 皇后、数独：搜索路径上每个状态几乎只走一次，子问题不重叠，回溯无需记忆化，加了也没用。
计数类问题（求方案数而非枚举方案）、最值类问题：往往子问题高度重叠，朴素回溯会指数爆炸，加记忆化立竿见影。

一个直观信号：如果你要的是「有多少种方案」而不是「列出所有方案」，几乎都该上记忆化。因为「列出」要求遍历每条路径（无法合并），而「计数」可以「把子问题的答案相加/相乘」，天然可合并、可缓存。

示例：目标和（计数问题）

给定数组 nums 和目标 target，给每个数前添加 + 或 -，求使表达式结果等于 target 的方案数。

朴素回溯：每个数两种选择， $O(2^n)$ ：

#include <vector>

class Solution {
    int count = 0;
    void backtrack(const std::vector<int>& nums, int i, int sum, int target) {
        if (i == (int)nums.size()) {
            if (sum == target) ++count;
            return;
        }
        backtrack(nums, i + 1, sum + nums[i], target);   // 选 +
        backtrack(nums, i + 1, sum - nums[i], target);   // 选 -
    }
public:
    int findTargetSumWays(std::vector<int>& nums, int target) {
        backtrack(nums, 0, 0, target);
        return count;
    }
};

n = 20 时 $2^{20} \approx 10^6$ 还能跑，但 n = 40 就彻底不行了。

记忆化回溯：观察状态 (i, sum) 会被大量重复到达——不同的 +/- 选择序列可能在同一位置达到同一 sum。用哈希表缓存 (i, sum) -> 方案数：

#include <vector>
#include <unordered_map>
#include <string>

class Solution {
    std::unordered_map<long long, int> memo;   // key = i * 偏移 + sum

    int backtrack(const std::vector<int>& nums, int i, int sum, int target) {
        if (i == (int)nums.size()) return sum == target ? 1 : 0;
        long long key = (long long)i * 2001LL + (sum + 1000);  // sum 偏移到非负
        auto it = memo.find(key);
        if (it != memo.end()) return it->second;
        int add = backtrack(nums, i + 1, sum + nums[i], target);
        int sub = backtrack(nums, i + 1, sum - nums[i], target);
        return memo[key] = add + sub;          // 记忆化：缓存并合并子问题答案
    }
public:
    int findTargetSumWays(std::vector<int>& nums, int target) {
        memo.clear();
        return backtrack(nums, 0, 0, target);
    }
};

关键变化：

函数从「遍历路径、累加全局 count」变成「返回以当前状态出发的方案数」。这是从「枚举」到「计数」的范式转换——回溯收集路径，记忆化收集「子问题的答案」。
进入函数先查 memo，命中直接返回；算完写入 memo。
子问题答案合并（add + sub）而非「遍历后回溯」。

复杂度从 $O(2^n)$ 降到 $O(n \cdot S)$ ，其中 $S$ 是 sum 的取值范围。这就是记忆化的威力：把指数级树压成多项式级表。

记忆化回溯 = 自顶向下 DP

把上面 backtrack 的递推关系写出来：dp(i, sum) = dp(i+1, sum+nums[i]) + dp(i+1, sum-nums[i])，边界 dp(n, sum) = (sum == target)。这正是 DP 的状态转移方程，只不过我们用「递归 + 缓存」自顶向下地求，而不是用循环自底向上地填。

两者的取舍：

记忆化回溯更贴近问题的自然递归结构，只计算真正到达的状态，写起来直观，适合状态稀疏或转移不规则的问题。
自底向上 DP无递归开销，常数更小，适合状态稠密、转移规整的问题，且易于做空间滚动优化。

工程上一种常见模式是：先用回溯写对暴力版本（保证正确性），再观察到重叠子问题，加记忆化优化（保证效率），最后若需要可改写成迭代 DP。这个「回溯 → 记忆化 → DP」的演进路径，是理解许多经典 DP 题的最自然方式。

需要注意的是，当问题要求「列出所有方案」时，记忆化无能为力——因为方案数量本身可能是指数级，你无法把它们压成多项式。记忆化只对「可合并的聚合量」（计数、最值、可行性布尔）有效。这是回溯与 DP 的根本分界：枚举用回溯，聚合用 DP。

横向对比：回溯、DP、贪心、分支限界

把回溯放进更大的搜索/优化算法版图里看：

维度	回溯	动态规划	贪心	分支限界
搜索方式	DFS	填表（通常自底向上）	单向前进	BFS/优先队列
状态空间	隐式决策树	显式状态表	单条路径	隐式搜索树
是否回退	是（撤销选择）	否	否	是（换分支）
适用	枚举所有解 / 找可行解	最优子结构 + 重叠子问题	贪心选择性质	最优化 + 强剪枝
典型问题	全排列、N 皇后、数独	背包、LCS、最短路	活动选择、Huffman	TSP、最短路径
复杂度	指数（剪枝压常数）	多项式	多项式	指数（剪枝压常数）

几个易混点的澄清：

回溯 vs 分支限界：都是搜索隐式树，回溯用 DFS（省内存、易写），分支限界用 BFS/优先队列（找最短/最优解时更早剪枝，但内存开销大）。求「所有解」几乎都用回溯，求「最优解」两者皆可，分支限界常配合更强的下界估计。
回溯 vs DP：如前述，回溯枚举路径，DP 聚合子问题。能 DP 的问题往往也能回溯，但 DP 利用重叠子问题把指数压成多项式；反过来，无重叠子问题的枚举只能靠回溯。
回溯 vs 贪心：贪心不回退，一旦选择就不再撤销，因此只在「局部最优 = 全局最优」时正确；回溯会尝试所有选择，正确性更广但更慢。能用贪心的问题一定有更快的贪心解，回溯是「不确定能否贪心时的保底」。

实战场景：竞赛与工程应用

竞赛。回溯是算法竞赛的常客：

搜索题：N 皇后、数独、骑士周游、八数码，标准回溯 + 剪枝。
构造题：括号生成、复原 IP 地址、电话号码字母组合，本质是受限的回溯。
状压/位运算回溯： $n \le 20$ 的小规模搜索，用整数位表示状态，配合记忆化（Meet-in-the-Middle 也常与回溯结合）。
CSP（约束满足）：数独、图着色、调度，回溯 + MRV 启发式 + 约束传播是标准解法。

竞赛中回溯题的「手感」往往体现在剪枝：同一题朴素回溯 TLE、加一两个剪枝就 AC 的情况比比皆是。练回溯就是练「还能砍掉哪些分支」的嗅觉。

工程。回溯在工程里更多以「搜索 + 剪枝」的形态出现：

正则引擎：带回溯的 NFA 匹配，遇到 .* 这类贪婪/分支结构时回溯尝试，是回溯的典型工程实现（也是「正则灾难性回溯」问题的根源）。
编译器：语法分析中 PEG 解析器、回溯递归下降解析器，本质是带记忆化的回溯。
求解器：SAT/SMT 求解器、约束求解器（如 Google OR-Tools 的 CP-SAT）内部是高度优化的回溯 + 冲突学习（CDCL）。
游戏 AI：井字棋、五子棋的极小化极大搜索 + $\alpha$ - $\beta$ 剪枝，本质是回溯在博弈树上的变体。
路径规划：在状态空间不大时，DFS 回溯找一条可行路径仍是简单可靠的方案。
配置搜索：依赖解析、插件组合、参数调优中的「找一个满足所有约束的组合」，常用回溯。

一个工程教训：生产环境里要警惕回溯的指数爆炸。比如用户传入一个恶意正则触发灾难性回溯，或一个约束配置让求解器跑数小时不返回。给回溯加上「步数/时间上限」和「记忆化/缓存」是常见的防御手段。

常见陷阱与边界条件

回溯代码短小但极易写错。以下是高频踩坑点：

1. 忘记撤销选择。最经典的 bug。push_back 了却忘了 pop_back，或 swap 进去没 swap 回来，导致兄弟分支拿到被污染的状态。检查方法：每一处「做选择」必须能在紧邻的递归调用后找到对应的「撤销选择」，且作用于同一元素。

2. 撤销的位置错误。撤销必须放在 for 循环内部、递归调用之后，而不是循环外。放在循环外会导致只撤销最后一次，前几次的修改残留。模板里的缩进结构（做-递-撤在同一层）必须严格遵守。

3. 收集答案的时机。排列在叶子收集（path.size() == n），子集在每个节点收集（函数开头 push_back）。混淆会导致排列多收、子集少收。判断口径：若中间状态本身就是合法解，就在节点收集；若只有完整状态才合法，就在叶子收集。

4. 去重条件写反。排列用 !used[i-1]，子集/组合用 i > start。混用会产生重复或漏解。务必先排序（去重前提），再按问题类型选条件。

5. start 与 used 用错。顺序敏感（排列）用 used[] 每层从 0 枚举；顺序无关（组合、子集）用 start 往后枚举。用反会导致组合产生重复（[1,2] 和 [2,1] 都出现）或排列漏解。

6. 引用传递导致状态污染。backtrack(nums, ...) 里 nums 用引用传递时，修改必须在递归前后成对还原。若某分支忘记还原，会污染整棵树。交换法全排列之所以容易错，正是因为 swap 修改了原数组。

7. 排序的副作用。去重剪枝要求先排序，但若题目要求「保持原顺序」或「按原下标」则不能直接排序，需用「下标数组」绕开。

8. 递归终止条件越界。start == nums.size() 与 start > nums.size() 的差别：写成 > 在某些写法下会漏收最后一个，写成 == 通常正确。子集问题不靠 start == size 终止（靠循环自然结束），但写 == size 提前返回也无妨。

9. isValid 的检查范围。N 皇后里只查上方，是因为下方还没放；若改成「全棋盘扫描」虽正确但浪费。要理解剪枝检查依赖「放置顺序」这一隐含假设。

10. 原地修改的恢复。单词搜索里 board[x][y] = '#' 标记访问，必须在所有递归路径（包括提前 return true 的成功路径）后恢复——不过求一个解时成功路径直接返回不恢复也无妨（反正不再用）；但求所有解时必须严格恢复，否则后续搜索会读到 '#'。这是「求一解」与「求全解」在代码上的微妙差异。

11. 整数溢出与下标。组合总和里 target - candidates[i] 若 candidates 含负数会无限递归；位运算 N 皇后里 (1 << n) - 1 当 n 接近 32/64 时要用对应宽度的类型。这些边界在面试和竞赛中常被故意构造。

小结

回溯算法的三句话本质：

它是在隐式决策树上的 DFS：把问题建模成「每一步做一个选择」的树，深度优先地遍历。
三段式模板：做选择 → 递归 → 撤销选择：用共享的可变状态承载路径，靠「撤销」保证兄弟分支互不干扰。
剪枝决定效率：可行性、去重、界限、剩余量、启发式排序，越早砍掉无望子树，实际规模越小。

掌握回溯的路径：先把通用模板刻进肌肉记忆，再分三类（排列用 used、组合子集用 start）吃透去重与收集时机，接着用 N 皇后、数独、单词搜索、分割回文串练剪枝嗅觉，最后理解「回溯 → 记忆化 → DP」的演进，知道何时该升级。

回溯不追求「更优的复杂度」（最坏仍是指数），而追求「把常数和实际触发规模压到可接受」。它是算法工具箱里「保底的暴力」——当问题没有更好的结构可利用时，回溯 + 剪枝几乎总能给出一个能跑的解；而当发现重叠子问题时，它又能自然演化成 DP。这种「从暴力出发、逐步优化」的思维方式，比任何一个具体算法都更值得内化。