01、回溯基础知识
大约 7 分钟数据结构算法算法基地面试回溯刷题程序厨校招社招
哈喽，大家好，我是厨子，今天给大家详细说一下回溯
什么是回溯算法
基本概念
回溯算法（Backtracking）：
一种通过探索所有可能的候选解来找出所有解的算法。
核心思想：
"试错" + "撤销"
过程：
1. 做出选择
2. 递归进入下一步
3. 撤销选择（回溯）
4. 尝试其他选择
大家应该都玩过走迷宫的游戏，主要流程如下
走迷宫：
你在迷宫里寻找出口：
1. 选择一条路走下去
2. 如果走到死路，退回上一个路口
3. 选择另一条路继续尝试
4. 重复直到找到出口或尝试完所有路
回溯就是这个"退回上一个路口"的过程！
标记路径：
- 走过的路做标记 ✓
- 退回时擦除标记（撤销）
- 确保每条路都能被尝试
此时我们疑惑了，这不就是 DFS 吗？为什么称之为回溯呢？
相同点：
- 都是深度优先搜索
- 都使用递归
- 都有回退过程
不同点：
DFS:通常用来解决路径搜索，连通性等问题，通常不用剪枝
回溯：通常用来解决，排列组合，子集相关问题，经常需要剪枝（提升性能）
简单理解：
回溯 = DFS + 状态恢复 + 剪枝
回溯过程就是遍历决策树，下面我们通过一个例子来看一下
示例：从 [1,2,3] 中选 2 个数的组合
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
路径记录：
第1层: 选择 1 → path = [1]
第2层: 选择 2 → path = [1,2] → 找到解！→ 回溯
第2层: 选择 3 → path = [1,3] → 找到解！→ 回溯
第1层: 回溯到 []
第1层: 选择 2 → path = [2]
第2层: 选择 3 → path = [2,3] → 找到解！→ 回溯
...
关键操作：
→ : 做选择（递归）
← : 撤销选择（回溯）
下面我们来说一下回溯的三要素
回溯三要素
要素1：路径
路径：已经做出的选择
表示方式：
1. vector：path = [1, 2, 3]
2. 字符串：path = "abc"
3. 状态变量：sum = 6, count = 3
作用：
- 记录当前状态
- 用于判断是否找到解
- 需要时保存到结果集
要素2：选择列表
选择列表：当前可以做的选择
示例：
- 排列问题：未使用的元素
- 组合问题：start 之后的元素
- 子集问题：当前元素及之后的元素
动态变化：
每一层的选择列表可能不同
- 已选择的元素不能再选（排列）
- 只能选择后面的元素（组合）
要素3：结束条件
结束条件：何时找到一个解
常见条件：
1. 路径长度达到要求
if (path.size() == k) return;
2. 满足特定条件
if (sum == target) return;
3. 遍历到叶子节点
if (index == n) return;
4. 无法继续选择
if (选择列表为空) return;
通过上面的例子，咱们是不是基本掌握了回溯的特性了，下面我们来看，回溯的核心框架模板
核心框架模板
void backtrack(路径, 选择列表) {
// 终止条件（找到一个解）
if (满足结束条件) {
result.add(路径);
return;
}
// 遍历所有选择
for (选择 in 选择列表) {
// 3. 剪枝（可选）
if (不满足条件) {
continue;
}
// 做选择
路径.add(选择);
// 或者标记：visited[选择] = true;
// 递归进入下一层
backtrack(路径, 新的选择列表);
// 撤销选择（回溯）
路径.remove(选择);
// 或者取消标记：visited[选择] = false;
}
}
下面继续带大家看一下常用回溯来解决的问题
子集问题
子集问题：
- 求所有可能的子集
- 每个元素选或不选
- 结果包含空集
示例：[1,2,3] 的所有子集
[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
组合问题
组合问题：
- 选出 k 个数的组合
- 不考虑顺序（[1,2] = [2,1]）
- 使用 start 避免重复
示例：从 [1,2,3,4] 选 2 个数
[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]
排列问题
问题特征
排列问题：
- 考虑顺序（[1,2] ≠ [2,1]）
- 每个元素只能用一次
- 需要 visited 数组标记
示例：[1,2,3] 的全排列
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
去重问题
问题特征
去重场景：
- 输入数组有重复元素
- 需要去掉重复的结果
示例：[1,2,2] 的组合
重复：[1,2], [1,2]
去重：[1,2]（只保留一个）
提到回溯，我们就离不开剪枝，下面，我们继续来说一下如何剪枝？剪枝的含义，就是省略掉那些不可能的遍历，已提升性能
剪枝优化技巧
提前终止
// 示例：组合总和
if (sum > target) {
return; // 已超过目标，直接返回
}
// 优化：排序后用 break
sort(candidates.begin(), candidates.end());
if (sum + candidates[i] > target) {
break; // 后面更大，直接 break
}
剪枝搜索空间
// 示例：组合问题
// 还需要 need = k - path.size() 个数
// 剩余元素至少要有 need 个
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
// ...
}
去重剪枝
// 树层去重
if (i > start && nums[i] == nums[i-1]) {
continue;
}
// 树枝去重
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
可行性剪枝
// 示例：N皇后
bool isValid(vector<string>& board, int row, int col) {
// 检查列冲突
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查对角线冲突
// ... 其他检查
return true;
}
// 在选择前就检查
if (!isValid(board, row, col)) {
continue; // 不合法，剪枝
}
也给大家整理了一下，刷题时的常见错误，大家可以提前避雷
常见错误
忘记回溯
// ✗ 错误：没有撤销选择
void backtrack(...) {
path.push_back(num);
backtrack(...);
// 忘记 path.pop_back();
}
// ✓ 正确
void backtrack(...) {
path.push_back(num);
backtrack(...);
path.pop_back(); // 必须撤销
}
去重条件错误
// ✗ 错误：i > 0 应该是 i > start
if (i > 0 && nums[i] == nums[i-1]) continue;
// ✓ 正确：树层去重
if (i > start && nums[i] == nums[i-1]) continue;
start 参数传递错误
// 组合问题
backtrack(i + 1); // ✓ 正确：下一层从 i+1 开始
// 排列问题
backtrack(0); // ✓ 正确：每层都从 0 开始
终止条件不完整
// ✗ 错误：没有 return
if (path.size() == k) {
result.push_back(path);
// 忘记 return;
}
// ✓ 正确
if (path.size() == k) {
result.push_back(path);
return; // 必须返回
}
那此时又问了，我理解回溯了，那什么时候使用回溯？回溯用来解决什么问题呢？
问题识别技巧
如何判断使用回溯？
关键词识别：
"所有可能的..."
"所有方案"
所有组合/排列/子集"
"找出所有满足条件的..."
问题特征：
需要穷举所有可能
有多个决策点
需要尝试+撤销
可以画出决策树
典型题型：
1. 排列组合子集
2. 棋盘问题（N皇后、数独）
3. 路径问题（所有路径）
4. 分割问题（分割字符串）
大家以后遇到带有上述关键字的题目时，要第一时间想到使用回溯哈
