主要参考的是 liweiwei、代码随想录、0x3F
回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的 递归 方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确的答案
- 在尝试了所有可能的分步方法后宣告该问题没有答案
深度优先搜索 算法（Depth-First-Search，DFS）是一种用于 遍历或搜索树或图 的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
典型的 DFS 但是没有回溯的题目：17. 电话号码的字母组合
简单比较
「回溯算法」与「深度优先遍历」都有**「不撞南墙不回头」**的意思。「回溯算法」强调了「深度优先遍历」思想的用途，用一个 不断变化 的变量，在尝试各种可能的过程中，搜索需要的结果。
- 回溯强调了 回退 操作对于搜索的合理性
- DFS 强调一种 遍历 的思想，与之对应的遍历思想是 BFS
1. 例题（46.全排列）
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
这是一到回溯算法的入门题，很好的说明了回溯算法在选择回退时的用法，几个比较重要的点是：
- 递归的重点条件是排列中数字已经选满
- 需要使用 used 来标记 path 使用过的变量
class Solution {
vector<vector<int>> res;
vector<int> path;
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<int> used(nums.size(), 0);
backtrace(nums, used);
return res;
}
void backtrace(vector<int>& nums, vector<int>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++ i) {
if (used[i]) continue; // path 中已经存在 nums[i] 直接跳过
path.push_back(nums[i]);
used[i] = 1;
backtrace(nums, used);
used[i] = 0; // 恢复现场
path.pop_back();
}
}
};另外在 C++ 里，最好还是不要写
vector<bool>，因为vector<bool>返回的是一个std::vector<bool>::reference的对象，数据量大时比vector<int>要慢，参考
有重复元素的全排列（LC.47）
- 排序之后再根据
nums[i-1]==nums[i]判重 - 在上一个相同的元素撤销之后去重效率更高
组合问题的排列（LC.39）
- 排列问题：讲究顺序，例如 [LC46.全排列]（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组
- 组合问题：不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量
有一个小经验就是 used 数组 和 begin 变量 一般不用一起使用
| 题目 | 说明 | 题解 |
|---|---|---|
| 78. 子集 | 和 LC.39 类似，按照 begin 为起点遍历回溯就可以 | 通过 |
| 90. 子集 II | 在 LC.78 的基础上有重复元素的考虑，和 LC.40 类似的剪枝 🔥 | 通过 |
| 131. 分割回文串 | 枚举字符之间的逗号，按照 idx 顺序回溯，判断回文 | 通过 |
| 698. 划分为k个相等的子集 | 抽象成 k 个桶，每个桶的容量为子集和大小 | 通过 |
| 473. 火柴拼正方形 | 和 LC.698 一模一样，抽象成 4 个桶 | 通过 |
| 2305. 公平分发饼干 | k 个桶，但是桶大小未知，从大到小DFS回溯 | 通过 |
| 854. 相似度为 K 的字符串 | DFS 回溯，剪枝，有点难... | 通过 |
| 1255. 得分最高的单词集合 | 参考灵神的子集型回溯，选或不选的思想，注意恢复现场 🔥 | 0x3F |
参考灵神思路总结一下：
- 输入视角：第 i 个元素「选还是不选」，这个比较直接
- 答案视角：第 i 个元素「枚举选哪个数」，也之前都是这个思路，也就是 begin 变量规定顺序
参考代码随想录的剪枝技巧：
-
for 循环横向遍历，递归是纵向遍历
-
区分一下什么是 树枝去重 vs 树层去重
| 题目 | 说明 | 题解 |
|---|---|---|
| 39. 组合总和 | 组合问题需要按照某种顺序搜索：每一次搜索的时候设置 下一轮搜索的起点 begin，也可以排序之后加速剪枝 |
通过 |
| 40. 组合总和 II | 和 LC.39 区别是这个有重复元素，需要去掉当前层（for循环中）第二个数值重复的节点 🔥 | 剪枝 |
| 77. 组合 | 和 LC.39 类似，按照 begin 为起点遍历然后回溯就可以，剪枝：剩余元素个数需要多余 k | 通过 |
| 216. 组合总和 III | 和 LC.40 类似，这题没有重复元素，两个剪枝：小于最小的 || 大于最大的 🔥 | 0x3F |
| 22. 括号生成 | 直接 DFS 思路（选或不选）更简单，比较剩余左右括号数量剪枝 | LWW |
-
按照灵神的思路总结一下： 和子集型回溯类似，加剪枝技巧，有时候使用「选或者不选」的思路比较简单，比如 LC.22 括号生成，有时候使用「选哪一个」思路比较简单，比如 LC.131 分割回文子串，具体做题时需要按照题目意思选择比较直接的思路
-
参考代码随想录的去重思想：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
| 题目 | 说明 | 题解 |
|---|---|---|
| 46. 全排列 | 回溯入门问题，无重复元素的排列问题 | 通过 |
| 47. 全排列 II | 去重是关键，排序比较，上一个相同的元素撤销之后再剪枝 🔥 | 剪枝图 |
| 51. N 皇后 | 第 row 行填入 path[row] 这个数，求 path 满足条件的全排列 | Carl |
- 参考灵神的写法：感觉排列行回溯使用「选哪一个」的思路比较简单，使用 used 数组记录当前 path 中有哪些元素使用过了，然后恢复现场
- 参考代码随想录：注意 LC.47 中如果有重复元素需要使用
used[i-1] == false来限制同一层重复元素，说明 i-1 是之前「被恢复的」元素，已经使用过了，所以剪掉