算法题型：回溯算法
回溯算法
回溯算法是暴力算法的一种，实际效率并不高，只是一种没有办法的办法
1 解题步骤
回溯算法可以说就是递归 + for 循环，大多都可以抽象成树的形式，在上一章的基础上构建 for 循环
解决的都是在集合中递归查找⼦集，集合的⼤⼩就构成了树的宽度，递归的深度，构成的树的深度。
回溯算法三部曲：
- 回溯的返回一般都是
void，⼀般是先写逻辑，然后需要什么参数，就填什么参数 - 终止条件，一般是找到一个符合条件的数值的时候
- 遍历过程：横向外层
for遍历宽度，纵向递归遍历深度
void backtracking(参数) {
if (终⽌条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}2 题目选取
2.1 组合总和 II
带去重的组合，需要理解组合的本质
同一层上，不允许取两个相同的数：因为不同 case 取同一个数，本质没有区别
在深度上，允许取两个相同的数字：因为同一个 case 内，同个数字取值本质上有区别
注意：树层的去重，需要进行排序
class Solution {
/*
横向不允许相同数字，去重需要排序
纵向允许相同数字，用 start 实现
*/
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
path.clear();
ret.clear();
sort(candidates.begin(), candidates.end());
traceback(0, candidates, target);
return ret;
}
vector<bool> used;
vector<int> path;
vector<vector<int>> ret;
void traceback(int start, const vector<int>& candidates, int remain) {
if (remain < 0) return;
if (remain == 0) {
ret.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
// 注意这里的去重逻辑，要和 start 比较
if (i > start && candidates[i - 1] == candidates[i]) {
// 表示存在上一个数字, 且相等，横向跳过，不可以修改循环边界 start
continue;
}
// 数组排序剪枝
if (candidates[i] > remain) break;
remain -= candidates[i];
path.push_back(candidates[i]);
// 纵向，使用 used 去重？
traceback(i + 1, candidates, remain);
remain += candidates[i];
path.pop_back();
}
}
};2.2 分割字符串类（回文串）
这类问题主要关注 不同的 path 定义，以及循环的条件
实际上就是放隔板问题，但是要考虑好隔板怎么能够在代码中实现
这里使用思路：左闭右开区间，左有两个索引固定，在循环开始时候分割，重点位置在注释中标出
class Solution {
public:
vector<vector<string>> partition(string s) {
auto curr = s.begin();
traceback(s, curr);
return ret;
}
vector<vector<string>> ret;
vector<string> path;
void traceback(const string& s, string::iterator curr) {
if ((curr - s.begin()) >= s.size()) {
// 数量满足，终止条件
ret.push_back(path);
return;
}
// 这里的 for 循环已经实现了 + 1 逻辑，外层不能 + 1
// 左闭右开区间，+ 1 代表仅纳入了一个字符
for (auto i = curr + 1; i <= s.end(); i++) {
if (is_palindrome(curr, i)) {
// 是回文，加入并递归，（也就是先判断再加入组合 path）
path.push_back(string(curr, i));
traceback(s, i); // 左闭右开， + 1 逻辑在 for 循环实现
path.pop_back();
} else {
continue;
}
}
}
bool is_palindrome(string::iterator first, string::iterator last) {
if (first == last) return true; // 空串
--last; // 右开变右闭
while (first < last) {
if (*first != *last)
return false;
++first;
--last;
}
return true;
}
};2.3 非递减子序列
本题是横向去重的典型例子
主要在于如何进行层内去重，重点是掌握层内的作用区间：for 循环内，调用递归值之前
#include <vector>
#include <unordered_set>
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
ret.clear();
path.clear();
backtrack(0, INT_MIN, nums);
return ret;
}
vector<vector<int>> ret;
vector<int> path;
void backtrack(int start, int pre, vector<int>& nums) {
// pre 代表上一数字
if (path.size() > 1) {
ret.push_back(path);
}
int i = start;
unordered_set<int> used; // 递归层内变量
for (int i = start; i < nums.size(); i++) {
// 本层内去重
if (used.count(nums[i])) continue;
if (pre > nums[i]) continue;
used.insert(nums[i]);
path.push_back(nums[i]);
backtrack(i + 1, nums[i], nums);
path.pop_back();
}
}
}; 2.4 全排列去重
非常独特的一个横纵结合的去重逻辑
排列不可以使用 startIndex，因为要遍历所有的节点
纵向不可以使用用过的下标值
横向去重需要考虑纵向是否使用过该数值，使用过则解禁，没用过则需要去重
注意条件满足需要返回，因为需要在叶子节点切断递归
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
ret.clear();
path.clear();
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
traceback(used, nums);
return ret;
}
vector<vector<int>> ret;
vector<int> path;
// 纵向不可以使用相同元素
// 横向去除同数值但下标不同元素
void traceback(vector<bool>& used, const vector<int>& nums) {
if (path.size() == nums.size()) {
ret.push_back(path);
return; // 这里要切断递归，是终止条件
}
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
// 指的是纵向没有使用过，并且横向数值相同（所以要排序）
// 纵向使用过就可以再次使用了
continue;
}
if (used[i]) continue; // 纵向去重
int curr = nums[i];
path.push_back(curr);
used[i] = true;
traceback(used, nums);
used[i] = false;
path.pop_back();
}
}
};3 总结
3.1 什么时候需要 startIndex？
需要横向去重的时候，有时候会配合排序来执行数值去重
3.2 纵向横向去重分别怎么实现？
3.2.1 纵向
纵向去重，使用 bool 类型 used 标记即可，注意 used 是全局变量
vector<bool> used; // 需要初始化为全 fasle
void backtrace() {
if (...) {}
for (int i = 0; i < value.size(); i++) {
if (used[i]) continue;
used[i] = true;
backtrace(); // 使用 used 包裹，回溯退出需要回退状态
used[i] = false;
}
}3.2.2 横向
- 没有重复元素，在递归时候传递
startIndex + 1即可
void backtrace(int startIndex) {
if (...) {}
for (int i = startIndex; i < end; i++) {
...;
backtrace(startIndex + 1);
...;
}
}- 有重复元素，可以排序后额外判断与上一个是否相等
sort(value.begin(), value.end());
void backtrace(int startIndex) {
if (...) {}
for (int i = startIndex; i < value.size(); i++) {
if (i > 0 && value[i] == value[i - 1]) continue; // 去重
...;
backtrace(startIndex + 1);
}
}3.3 返回值
3.3.1 什么时候 return
return 的唯一逻辑是：
- 无路可走
- 这条节点已经失败了
3.3.2 不同位置的 return
if终止条件：- 需要继续搜索 → return（存答案以后继续兄弟分支）
- 不需要继续搜索 → return true（直接停止整个搜索）
for循环内部：- 当前分支无效但下一分支还有希望 → continue
- 当前分支无效且后续分支也无希望 → return（剪枝）
如果需要获取所有节点，可以在 if 下写 return 而是通过 for 的逻辑进行控制
3.3.3 返回值设置
绝大多数情况都是 void
除非找到一种情况立刻返回，此时使用 bool，同时递归写法也会改变
if (traceback(...)) return true;