第八章 回溯算法¶
本章目标：理解回溯算法的核心思想——"选择-探索-撤销"模式，掌握子集、排列、组合三大经典问题框架，学会 N 皇后、解数独等棋盘问题，并灵活运用剪枝策略优化搜索效率。
8.1 回溯算法框架：选择-探索-撤销 模式¶
8.1.1 什么是回溯¶
回溯（Backtracking）是一种通过穷举所有可能来寻找解的算法思想。它的本质是一棵决策树的深度优先遍历：在每个节点做出一个选择，递归进入下一层探索，探索完毕后撤销选择（回退），尝试下一个分支。
回溯的直觉理解
想象你在走迷宫：走到一个岔路口，先选左边走到底，如果走不通就退回来再走右边。回溯就是系统性地"试错"——走不通就回头，换条路再试。
回溯算法的核心框架可以概括为三个步骤：
graph TD
A["开始：空路径"] --> B["做出选择 (Choose)"]
B --> C["递归探索 (Explore)"]
C --> D{"是否满足结束条件?"}
D -->|是| E["记录结果"]
D -->|否| B
E --> F["撤销选择 (Unchoose)"]
F --> G["尝试下一个选择"]
G --> B
F --> H["回溯到上一层"]8.1.2 通用回溯框架¶
回溯算法有一个高度统一的模板，所有回溯问题都可以在此基础上修改：
#include <bits/stdc++.h>
using namespace std;
// 结果集：存储所有合法解
vector<vector<int>> res;
// 当前路径：记录已经做出的选择
vector<int> path;
// 回溯函数
// 参数说明：
// - startIndex: 选择的起始位置，避免重复选择
// - 其他问题特定参数（如目标和、剩余长度等）
void backtrack(vector<int>& nums, int startIndex) {
// 1. 结束条件：判断当前路径是否构成一个合法解
if (/* 满足结束条件 */) {
res.push_back(path); // 收集结果
return; // 不再继续探索
}
// 2. 遍历选择列表：从 startIndex 开始，避免重复
for (int i = startIndex; i < nums.size(); i++) {
// 剪枝：跳过不合法的选择（可选）
if (/* 需要剪枝 */) continue;
// 3. 做选择：将当前元素加入路径
path.push_back(nums[i]);
// 4. 递归探索：进入下一层决策
backtrack(nums, i + 1); // 注意：子集问题用 i+1，排列问题从 0 开始
// 5. 撤销选择：将当前元素从路径中移除（回溯）
path.pop_back();
}
}
回溯三要素缺一不可
- 结束条件：决定了什么时候停止递归、收集结果
- 选择列表：在当前状态下还有哪些可做的选择
- 撤销操作：保证回到上一个状态，尝试其他分支
8.1.3 回溯的执行过程图解¶
以数组 [1, 2, 3] 求所有子集为例，回溯的完整执行过程如下：
graph TD
R["[] (根节点)"] --> A1["选择1 → [1]"]
R --> A2["选择2 → [2]"]
R --> A3["选择3 → [3]"]
A1 --> B12["选择2 → [1,2]"]
A1 --> B13["选择3 → [1,3]"]
A2 --> B23["选择3 → [2,3]"]
B12 --> C123["选择3 → [1,2,3]"]每一条从根到任意节点的路径都代表一个子集。回溯就是系统性地遍历这棵树的所有节点。
时间复杂度估算
回溯算法的时间复杂度通常取决于决策树的节点总数。对于 n 个元素的子集问题，决策树有 \(2^n\) 个节点（每个元素选或不选），因此时间复杂度为 \(O(2^n)\)。
8.2 回溯三问：路径、选择列表、结束条件¶
在动手写代码之前，面对任何回溯问题，都应该先回答三个问题：
8.2.1 三问详解¶
| 问题 | 含义 | 举例（子集问题） |
|---|---|---|
| 路径（Path） | 已经做出的选择 | 当前已经选了 [1, 3] |
| 选择列表（Choices） | 当前还能做哪些选择 | 还可以选择 [2, 4, 5] 中的元素 |
| 结束条件（Base Case） | 什么时候到达决策树底部 | 所有元素都已考虑过（选或不选） |
graph TD
subgraph "回溯三问"
P["路径 Path<br/>记录已做的选择"]
C["选择列表 Choices<br/>当前可做的选择"]
B["结束条件 Base Case<br/>何时收集结果"]
end
P -->|决策| C
C -->|到达底部| B
B -->|回退| P8.2.2 三问的变体¶
不同问题的"结束条件"和"选择列表"会有不同：
| 问题类型 | 路径 | 选择列表 | 结束条件 |
|---|---|---|---|
| 子集 | 已选元素 | 剩余元素 | 所有元素考虑完毕 |
| 排列 | 已排列元素 | 未使用的元素 | 路径长度等于 n |
| 组合 | 已选 k 个元素 | 剩余元素 | 路径长度等于 k |
| N 皇后 | 已放置的皇后 | 当前行可放的列 | n 行全部放完 |
| 分割 | 已分割的子串 | 剩余子串 | 字符串用完 |
万能解题法
遇到回溯问题时，先画出决策树，再把三个要素对应到树上的结构： - 路径 = 根到当前节点的路径 - 选择列表 = 当前节点可以延伸的分支 - 结束条件 = 到达叶子节点（或满足某个条件）
8.3 子集问题：无重复元素、有重复元素¶
8.3.1 无重复元素的子集（LeetCode 78）¶
问题描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集。
思路分析：
对于数组中的每个元素，我们有两个选择：选 或 不选。这构成一棵二叉决策树。
graph TD
R["起点"] --> S1["考虑 nums[0]=1"]
S1 -->|选1| S2["考虑 nums[1]=2, 路径=[1]"]
S1 -->|不选1| S3["考虑 nums[1]=2, 路径=[]"]
S2 -->|选2| S4["考虑 nums[2]=3, 路径=[1,2]"]
S2 -->|不选2| S5["考虑 nums[2]=3, 路径=[1]"]
S3 -->|选2| S6["考虑 nums[2]=3, 路径=[2]"]
S3 -->|不选2| S7["考虑 nums[2]=3, 路径=[]"]
S4 -->|选3| R1["[1,2,3]"]
S4 -->|不选3| R2["[1,2]"]
S5 -->|选3| R3["[1,3]"]
S5 -->|不选3| R4["[1]"]
S6 -->|选3| R5["[2,3]"]
S6 -->|不选3| R6["[2]"]
S7 -->|选3| R7["[3]"]
S7 -->|不选3| R8["[]"]代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res; // 存储所有子集
vector<int> path; // 当前子集
// 回溯函数：从 startIndex 开始考虑每个元素
void backtrack(vector<int>& nums, int startIndex) {
// 每个节点都代表一个合法子集，直接加入结果
// 注意：这里不需要额外的结束条件判断
res.push_back(path);
// 遍历选择列表：从 startIndex 开始
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]); // 做选择
backtrack(nums, i + 1); // 递归：从下一个位置开始
path.pop_back(); // 撤销选择
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0);
return res;
}
};
int main() {
Solution sol;
vector<int> nums = {1, 2, 3};
vector<vector<int>> ans = sol.subsets(nums);
for (auto& subset : ans) {
cout << "[";
for (int i = 0; i < subset.size(); i++) {
cout << subset[i] << (i + 1 < subset.size() ? "," : "");
}
cout << "] ";
}
// 输出: [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3]
return 0;
}
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n \times 2^n)\) | 共 \(2^n\) 个子集，每个子集最多 n 个元素 |
| 空间 | \(O(n)\) | 递归栈深度为 n（不计结果存储空间） |
为什么子集问题的每个节点都要收集结果？
子集问题的解包括所有节点（不仅仅是叶子节点），因为路径 []、[1]、[1,2] 本身都是合法子集。而排列和组合问题通常只在叶子节点收集结果。
8.3.2 有重复元素的子集（LeetCode 90）¶
问题描述：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（结果不能包含重复子集）。
关键技巧：先对数组排序，然后在同一层循环中，如果当前元素与前一个元素相同，则跳过。
graph TD
R["nums = [1,2,2], 排序后不变"] --> L1["第1层: 选1"]
R --> L2["第1层: 选2(第一个)"]
R --> L3["第1层: 选2(第二个) — 剪枝! 同层重复"]
L1 --> L12["第2层: 选2(第一个)"]
L1 --> L13["第2层: 选2(第二个)"]
L12 --> L123["第3层: 选2(第二个)"]代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& nums, int startIndex) {
res.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// 剪枝：同一层中，跳过重复元素
// i > startIndex 保证是"同一层"而不是"同一枝"
if (i > startIndex && nums[i] == nums[i - 1]) {
continue;
}
path.push_back(nums[i]);
backtrack(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序，让相同元素相邻
backtrack(nums, 0);
return res;
}
};
同层剪枝 vs 同枝剪枝
- 同层剪枝：
if (i > startIndex && nums[i] == nums[i-1])— 跳过同一层的重复元素 - 同枝剪枝：在同一递归路径中允许重复（比如组合总和中一个元素可以用多次）
- 区分方法：
i > startIndex表示当前不是第一次在这个递归层选择
8.4 排列问题：无重复元素、有重复元素¶
8.4.1 无重复元素的排列（LeetCode 46）¶
问题描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
与子集问题的关键区别：
| 对比项 | 子集问题 | 排列问题 |
|---|---|---|
| 元素顺序 | 无关（[1,2] = [2,1]） |
有关（[1,2] ≠ [2,1]） |
| startIndex | 需要（避免重复） | 不需要（每层从 0 开始） |
| 标记数组 | 不需要 | 需要（标记已使用的元素） |
graph TD
R["路径=[]"] --> A1["选1 → [1]"]
R --> A2["选2 → [2]"]
R --> A3["选3 → [3]"]
A1 --> B12["选2 → [1,2]"]
A1 --> B13["选3 → [1,3]"]
A2 --> B21["选1 → [2,1]"]
A2 --> B23["选3 → [2,3]"]
A3 --> B31["选1 → [3,1]"]
A3 --> B32["选3 → [3,2]"]
B12 --> R123["[1,2,3] ✅"]
B13 --> R132["[1,3,2] ✅"]
B21 --> R213["[2,1,3] ✅"]
B23 --> R231["[2,3,1] ✅"]
B31 --> R312["[3,1,2] ✅"]
B32 --> R321["[3,2,1] ✅"]代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& nums, vector<bool>& used) {
// 结束条件：路径长度等于数组长度，说明所有元素都已排列
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
// 每一层从 0 开始遍历所有元素
for (int i = 0; i < nums.size(); i++) {
// 跳过已经在路径中的元素
if (used[i]) continue;
// 做选择
used[i] = true;
path.push_back(nums[i]);
// 递归探索
backtrack(nums, used);
// 撤销选择
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false); // 标记数组
backtrack(nums, used);
return res;
}
};
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n \times n!)\) | 共 n! 个排列，每个排列长度为 n |
| 空间 | \(O(n)\) | 递归栈深度 + used 数组 |
8.4.2 有重复元素的排列（LeetCode 47）¶
问题描述：给定一个可包含重复数字的序列 nums，返回所有不重复的全排列。
关键技巧：排序 + 同层剪枝。同一层中，如果当前元素和前一个相同，且前一个没有被使用（说明前一个在同层已被回溯），则跳过。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 跳过已使用的元素
if (used[i]) continue;
// 同层去重：nums[i] == nums[i-1] 且 nums[i-1] 没被使用
// 说明 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.pop_back();
used[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序是去重的前提
vector<bool> used(nums.size(), false);
backtrack(nums, used);
return res;
}
};
排列去重的关键判断
!used[i-1] 是核心！如果写成 used[i-1]，那就变成了"同枝去重"，会错误地剪掉合法排列。记住：
- !used[i-1] → 前一个元素已经回溯了 → 同层重复 → 应该跳过
- used[i-1] → 前一个元素还在路径中 → 同枝 → 不应该跳过
8.5 组合问题：组合总和系列¶
8.5.1 组合（LeetCode 77）¶
问题描述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
graph TD
R["n=4, k=2"] --> A1["选1"]
R --> A2["选2"]
R --> A3["选3"]
R --> A4["选4"]
A1 --> B12["选2 → [1,2] ✅"]
A1 --> B13["选3 → [1,3] ✅"]
A1 --> B14["选4 → [1,4] ✅"]
A2 --> B23["选3 → [2,3] ✅"]
A2 --> B24["选4 → [2,4] ✅"]
A3 --> B34["选4 → [3,4] ✅"]代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(int n, int k, int startIndex) {
// 剪枝：剩余元素不够凑齐 k 个，直接返回
// 还需要 (k - path.size()) 个元素
// 可选范围是 [startIndex, n]，共 (n - startIndex + 1) 个
if (path.size() + (n - startIndex + 1) < k) {
return;
}
// 结束条件：已选 k 个元素
if (path.size() == k) {
res.push_back(path);
return;
}
// 遍历选择列表
// 优化：i <= n - (k - path.size()) + 1，避免无效遍历
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.push_back(i);
backtrack(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtrack(n, k, 1);
return res;
}
};
| 复杂度 | 值 |
|---|---|
| 时间 | \(O(C(n,k) \times k)\) |
| 空间 | \(O(k)\) |
组合问题的剪枝优化
当 for 循环的起始值 i 满足 i > n - (k - path.size()) + 1 时，剩余元素不够组成 k 个，可以提前终止。这个剪枝在 n 较大、k 较小时效果显著。
8.5.2 组合总和（LeetCode 39）¶
问题描述：给定一个无重复元素的候选数组 candidates 和目标数 target，找出所有使数字之和为目标数的组合。同一个数字可以无限制重复被选取。
graph TD
R["target=7, candidates=[2,3,6,7]"] --> A1["选2, 剩余5"]
R --> A2["选3, 剩余4"]
R --> A3["选6, 剩余1"]
R --> A4["选7, 剩余0 ✅ → [7]"]
A1 --> B11["再选2, 剩余3"]
A1 --> B12["选3, 剩余2"]
A1 --> B13["选6, 剩余-1 ✗"]
B11 --> C111["再选2, 剩余1"]
B11 --> C112["选3, 剩余0 ✅ → [2,2,3]"]
C111 --> D1111["再选2, 剩余-1 ✗"]代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& candidates, int target, int startIndex) {
// 结束条件：目标值为 0，找到一个合法组合
if (target == 0) {
res.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
// 剪枝：当前候选值已经超过剩余目标，不可能有解
// 前提：数组已排序
if (candidates[i] > target) break;
path.push_back(candidates[i]);
// 注意：这里传 i 而非 i+1，因为同一个数字可以重复使用
backtrack(candidates, target - candidates[i], i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtrack(candidates, target, 0);
return res;
}
};
递归参数 i vs i+1
- 传
i：同一元素可以重复使用（组合总和 I） - 传
i + 1：每个元素只能用一次（组合总和 II）
8.5.3 组合总和 II（LeetCode 40）¶
问题描述：给定一个有重复元素的候选数组 candidates 和目标数 target，找出所有使数字之和为目标数的组合。每个数字只能使用一次。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& candidates, int target, int startIndex,
vector<bool>& used) {
if (target == 0) {
res.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
// 剪枝：排序后，超过目标直接 break
if (candidates[i] > target) break;
// 同层去重：与子集 II 相同的逻辑
if (i > startIndex && candidates[i] == candidates[i - 1]
&& !used[i - 1]) {
continue;
}
used[i] = true;
path.push_back(candidates[i]);
// i + 1：每个元素只用一次
backtrack(candidates, target - candidates[i], i + 1, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<bool> used(candidates.size(), false);
backtrack(candidates, target, 0, used);
return res;
}
};
8.6 棋盘问题：N 皇后、解数独¶
8.6.1 N 皇后（LeetCode 51）¶
问题描述：在 n x n 的棋盘上放置 n 个皇后，使得它们互不攻击（不能在同一行、同一列、同一对角线）。
思路分析：逐行放置皇后。对于每一行，尝试每一列，检查是否与已放置的皇后冲突。
graph TD
subgraph "4皇后的一种解法"
direction LR
B1[". Q . .<br/>. . . Q<br/>Q . . .<br/>. . Q ."]
end
subgraph "冲突检测"
C1["同行冲突：同一行已有皇后"]
C2["同列冲突：同一列已有皇后"]
C3["同对角线冲突：行差=列差"]
endN 皇后棋盘可视化（n=4 的一种解）：
列: 0 1 2 3
行0: . Q . . ← 皇后在 (0,1)
行1: . . . Q ← 皇后在 (1,3)
行2: Q . . . ← 皇后在 (2,0)
行3: . . Q . ← 皇后在 (3,2)
检查对角线：
- (0,1) 和 (1,3)：行差=1，列差=2，不冲突 ✅
- (0,1) 和 (2,0)：行差=2，列差=1，不冲突 ✅
- (1,3) 和 (3,2)：行差=2，列差=1，不冲突 ✅
代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> res; // 存储所有解
// 检查在 (row, col) 位置放置皇后是否合法
bool isValid(vector<string>& board, int row, int col, int n) {
// 检查同列（只需检查上方，因为下方还没放）
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线 45 度
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线 135 度
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true; // 所有方向都没有冲突
}
// 回溯函数：从第 row 行开始放置皇后
void backtrack(vector<string>& board, int row, int n) {
// 结束条件：所有行都已放置皇后
if (row == n) {
res.push_back(board);
return;
}
// 尝试在当前行的每一列放置皇后
for (int col = 0; col < n; col++) {
// 检查当前位置是否合法
if (!isValid(board, row, col, n)) continue;
// 做选择：在 (row, col) 放置皇后
board[row][col] = 'Q';
// 递归：处理下一行
backtrack(board, row + 1, n);
// 撤销选择：移除皇后
board[row][col] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
// 初始化 n x n 棋盘，全部填 '.'
vector<string> board(n, string(n, '.'));
backtrack(board, 0, n);
return res;
}
};
int main() {
Solution sol;
auto ans = sol.solveNQueens(4);
for (auto& board : ans) {
cout << "====" << endl;
for (auto& row : board) {
cout << row << endl;
}
}
return 0;
}
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n!)\) | 第一行 n 种选择，第二行最多 n-1 种，... |
| 空间 | \(O(n^2)\) | 棋盘存储 |
优化：用三个集合加速冲突检测
可以用 colSet（列集合）、diag1Set（主对角线）、diag2Set（副对角线）来将 isValid 的 \(O(n)\) 检查优化到 \(O(1)\)：
- 列：直接查 colSet
- 主对角线（左上到右下）：row - col 的值相同
- 副对角线（右上到左下）：row + col 的值相同
// 优化版冲突检测：用集合代替逐格扫描
unordered_set<int> colSet, diag1Set, diag2Set;
// 放置皇后时
colSet.insert(col);
diag1Set.insert(row - col); // 主对角线标识
diag2Set.insert(row + col); // 副对角线标识
// 检查是否冲突
bool isValid(int row, int col) {
return colSet.count(col) == 0
&& diag1Set.count(row - col) == 0
&& diag2Set.count(row + col) == 0;
}
// 撤销时
colSet.erase(col);
diag1Set.erase(row - col);
diag2Set.erase(row + col);
8.6.2 解数独（LeetCode 37）¶
问题描述：编写一个程序，通过填充空格来解决数独问题。数独的规则：每行、每列、每个 3x3 宫格中，数字 1-9 各出现一次。
graph TD
A["找到一个空格 '.'"] --> B["尝试填入数字 1-9"]
B --> C{"该数字合法？"}
C -->|否| B
C -->|是| D["填入数字"]
D --> E["递归处理下一个空格"]
E --> F{"所有空格都填完了？"}
F -->|是| G["找到解！"]
F -->|否| A
D --> H["回溯：撤销填入"]
H --> B代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// 检查在 (row, col) 填入数字 digit 是否合法
bool isValid(vector<vector<char>>& board, int row, int col, char digit) {
for (int i = 0; i < 9; i++) {
// 检查行
if (board[row][i] == digit) return false;
// 检查列
if (board[i][col] == digit) return false;
// 检查 3x3 宫格
int boxRow = 3 * (row / 3) + i / 3;
int boxCol = 3 * (col / 3) + i % 3;
if (board[boxRow][boxCol] == digit) return false;
}
return true;
}
// 回溯函数：找到下一个空格并尝试填数
bool backtrack(vector<vector<char>>& board) {
// 遍历每个格子，找到第一个空格
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue; // 跳过已填的格子
// 尝试填入 '1' 到 '9'
for (char d = '1'; d <= '9'; d++) {
if (!isValid(board, i, j, d)) continue;
board[i][j] = d; // 做选择
if (backtrack(board)) {
return true; // 找到解，直接返回
}
board[i][j] = '.'; // 撤销选择
}
// 1-9 都不行，说明前面的选择有误，回溯
return false;
}
}
// 没有空格了，数独已解完
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtrack(board);
}
};
数独回溯 vs N 皇后
- N 皇后：需要收集所有解
- 数独：只需找到一个解，所以找到后立即
return true - 数独没有显式的
startIndex，因为每次都要遍历找空格
8.7 剪枝策略：排序剪枝、可行性剪枝、最优性剪枝¶
剪枝是回溯的灵魂。好的剪枝可以将搜索空间从指数级降到多项式级。
8.7.1 排序剪枝¶
原理：对数组排序后，可以在循环中利用 break / continue 提前终止无效搜索。
graph LR
A["排序前: [3,1,4,1,5]"] --> B["排序后: [1,1,3,4,5]"]
B --> C["遍历时超过目标 → break"]
C --> D["跳过同层重复 → continue"]// 组合总和 I 中的排序剪枝
sort(candidates.begin(), candidates.end());
for (int i = startIndex; i < candidates.size(); i++) {
// 排序后，一旦 candidates[i] > target，后面更大的也不用看了
if (candidates[i] > target) break; // 排序剪枝
path.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], i);
path.pop_back();
}
8.7.2 可行性剪枝¶
原理：在进入递归之前，先判断当前选择是否可能导致合法解。如果不可能，直接跳过。
// 组合问题中的可行性剪枝
// 如果剩余元素不够凑齐 k 个，直接返回
void backtrack(int n, int k, int startIndex) {
// 还需要选 (k - path.size()) 个元素
// 可选范围 [startIndex, n] 共 (n - startIndex + 1) 个
if (path.size() + (n - startIndex + 1) < k) {
return; // 可行性剪枝：剩余元素不够
}
if (path.size() == k) {
res.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i);
backtrack(n, k, i + 1);
path.pop_back();
}
}
8.7.3 最优性剪枝¶
原理：在求最优解（最小值/最大值）的问题中，如果当前路径的代价已经超过了已知最优解，就没必要继续探索。
// 示例：在回溯中维护全局最优解
int bestResult = INT_MAX;
void backtrack(vector<int>& nums, int currentCost, ...) {
// 最优性剪枝：当前代价已超过已知最优解
if (currentCost >= bestResult) {
return; // 剪枝
}
if (/* 满足结束条件 */) {
bestResult = min(bestResult, currentCost);
return;
}
for (...) {
// 尝试选择
backtrack(nums, currentCost + /* 新增代价 */, ...);
// 撤销选择
}
}
8.7.4 剪枝策略总结¶
| 剪枝类型 | 适用场景 | 关键操作 | 效果 |
|---|---|---|---|
| 排序剪枝 | 有序数组上搜索 | sort + break |
跳过无效分支 |
| 可行性剪枝 | 约束满足问题 | 条件判断 + continue/return |
避免进入不可能的分支 |
| 最优性剪枝 | 求最优解 | 维护全局最优 + return |
剪掉不会产生更优解的分支 |
| 去重剪枝 | 数组有重复元素 | 排序 + 同层跳过 | 避免生成重复解 |
剪枝的前提条件
- 排序剪枝需要数组有序
- 去重剪枝需要先排序
- 最优性剪枝需要先找到一个可行解作为初始 bound 错误的剪枝条件可能导致漏解！务必仔细验证剪枝的正确性。
8.8 回溯与其他算法的关系¶
8.8.1 回溯 vs DFS¶
回溯和 DFS（深度优先搜索）经常被混淆。它们的关系是：
graph TD
subgraph "关系图"
DFS["DFS（深度优先搜索）<br/>一种遍历/搜索策略"]
BT["回溯（Backtracking）<br/>一种求解问题的方法"]
DFS -->|"回溯使用 DFS 作为遍历策略"| BT
end
subgraph "区别"
D1["DFS 侧重：遍历图/树的每个节点"]
D2["回溯侧重：在遍历过程中做选择和撤销"]
end| 对比项 | DFS | 回溯 |
|---|---|---|
| 关注点 | 遍历所有可达节点 | 求解满足条件的路径/组合 |
| 是否做选择 | 不涉及"选择-撤销" | 核心是"选择-撤销"模式 |
| 结果 | 访问顺序/连通性 | 具体的解 |
| 典型应用 | 图遍历、连通分量 | 子集、排列、组合、N 皇后 |
8.8.2 回溯 vs 动态规划（DP）¶
回溯和动态规划都涉及"将问题分解为子问题"，但思路截然不同：
| 对比项 | 回溯 | 动态规划 |
|---|---|---|
| 求解方式 | 穷举所有可能 | 记忆化 / 递推 |
| 时间复杂度 | 通常指数级 | 通常多项式级 |
| 是否有重叠子问题 | 不处理，重复计算 | 利用 memo 或 dp 数组消除重复 |
| 适用场景 | 求所有解/枚举 | 求最优解/计数 |
| 实现方式 | 递归 + 剪枝 | 递推 or 记忆化搜索 |
graph LR
subgraph "回溯"
B1["穷举所有路径"]
B2["找到所有合法解"]
B3["指数时间"]
end
subgraph "动态规划"
D1["记录子问题结果"]
D2["合并得最优解"]
D3["多项式时间"]
end
B1 -->|"优化"| D1经典例子：
| 问题 | 回溯解法 | DP 解法 |
|---|---|---|
| 斐波那契数列 | 递归暴力 \(O(2^n)\) | dp 数组 \(O(n)\) |
| 0-1 背包 | 枚举所有组合 \(O(2^n)\) | dp 二维数组 \(O(nW)\) |
| 最长递增子序列 | 枚举所有子序列 \(O(2^n)\) | dp[i] \(O(n^2)\) |
何时用回溯，何时用 DP？
- 求所有解（列出所有排列、组合、子集）→ 回溯
- 求最优解（最大值、最小值）或方案数 → 动态规划
- 求一个可行解 → 两者都可以，优先考虑 DP（效率更高）
8.8.3 回溯 vs 分支限界¶
分支限界是回溯的"升级版"，结合了最优性剪枝的思想：
| 对比项 | 回溯 | 分支限界 |
|---|---|---|
| 搜索策略 | DFS（深度优先） | BFS / 优先队列（广度优先） |
| 剪枝方式 | 可行性剪枝 | 最优性剪枝（更激进） |
| 适用场景 | 枚举所有解 | 求最优解 |
| 典型应用 | 排列组合、N 皇后 | 旅行商问题、任务分配 |
练习题¶
LeetCode 暑假 backtracking¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 997 | Find the Town Judge | Easy | 链接 | - [ ] |
| 1700 | Number of Students Unable to Eat Lunch | Easy | 链接 | - [ ] |
| 1863 | Sum of All Subset XOR Totals | Easy | 链接 | - [ ] |
| 17 | Letter Combinations of a Phone Number | Medium | 链接 | - [ ] |
| 526 | Beautiful Arrangement | Medium | 链接 | - [ ] |
| 513 | Find Bottom Left Tree Value | Medium | 链接 | - [ ] |
| 1864 | Minimum Number of Swaps to Make the Binary String Alternating | Medium | 链接 | - [ ] |
| 473 | Matchsticks to Square | Medium | 链接 | - [ ] |
| 401 | Binary Watch | Easy | 链接 | - [ ] |
| 51 | N-Queens | Hard | 链接 | - [ ] |
| 301 | Remove Invalid Parentheses | Hard | 链接 | - [ ] |
| 679 | 24 Game | Hard | 链接 | - [ ] |
| 1467 | Probability of a Two Boxes Having The Same Number of Distinct Balls | Hard | 链接 | - [ ] |
| 2065 | Maximum Path Quality of a Graph | Hard | 链接 | - [ ] |
寒假回溯相关¶
以下题目虽然不直接以"回溯"标签出现，但其本质思想与回溯/DFS 一脉相承：
| 题号 | 题目 | 说明 | 链接 | 完成 |
|---|---|---|---|---|
| 94 | Binary Tree Inorder Traversal | 二叉树中序遍历，理解递归与回溯 | 链接 | - [ ] |
| 114 | Flatten Binary Tree to Linked List | 展平二叉树，前序遍历的回溯思维 | 链接 | - [ ] |
| 543 | Diameter of Binary Tree | 二叉树直径，DFS + 全局变量 | 链接 | - [ ] |
| 200 | Number of Islands | 岛屿数量，DFS/BFS 染色（类回溯） | 链接 | - [ ] |
寒假与暑假的衔接
寒假学习的 DFS 遍历（如树的遍历、岛屿问题）是回溯的基础。暑假的回溯专题在此基础上加入了选择-撤销机制和剪枝优化，解决更复杂的组合搜索问题。
本章小结¶
| 小节 | 核心内容 | 关键技巧 |
|---|---|---|
| 8.1 回溯框架 | 选择-探索-撤销 | 通用模板：递归 + 循环 + pop |
| 8.2 回溯三问 | 路径、选择列表、结束条件 | 先画决策树，再写代码 |
| 8.3 子集 | 无重复 / 有重复 | 每个节点收集结果；排序 + 同层去重 |
| 8.4 排列 | 无重复 / 有重复 | used 数组；!used[i-1] 去重 |
| 8.5 组合 | 组合总和系列 | startIndex；排序剪枝 |
| 8.6 棋盘 | N 皇后、数独 | isValid 检查；对角线公式 |
| 8.7 剪枝 | 排序/可行性/最优性 | 提前终止无效搜索 |
| 8.8 算法关系 | 回溯 vs DFS vs DP | 回溯求所有解，DP 求最优解 |