代码随想录算法训练营第19天 | 第七章 回溯算法part01
代码随想录算法训练营第19天 | 第七章 回溯算法part01
- 理论基础
- 77. 组合
- 216. 组合总和 III
- 17. 电话号码的字母组合
理论基础
其实在讲解二叉树的时候，就给大家介绍过回溯，这次正式开启回溯算法，大家可以先看视频，对回溯算法有一个整体的了解。
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。它的基本思想就是通过递归地选择并尝试解决问题的每个部分，当发现当前选择不符合条件时，会回退（撤销选择），然后继续尝试其他选择。回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了。
- 题目链接/文章讲解
- 视频讲解
77. 组合
对照回溯算法理论基础给出的代码模板，来做本题组合问题，大家就会发现写回溯算法的套路。
在回溯算法解决实际问题的过程中，大家会有各种疑问，先看视频介绍，基本可以解决大家的疑惑。
本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。
- 题目链接/文章讲解
- 视频讲解
- 剪枝操作讲解
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围,图中可以发现n相当于树的宽度，k相当于树的深度。每次搜索到了叶子节点，我们就找到了一个结果。
实际上看代码还算比较好理解，回溯的核心就是用完以后就扔了，push以后就pop，遍历下一个。
至于剪枝优化也很简单，主要是n - (k - path.size()) + 1。没优化前，i是一直要遍历到n。现在我们只要遍历到n - (k - path.size()) + 1即可。k - path.size()即为冗余，假设有n=10个元素，需要k=5个元素，已经取了path.size()=3个元素，这时候还需要去俩，那么前一步最多只能遍历到10-2=8，二现在这时候我们要从9开始取，所以再+1。当把代码思路整理了一下后，就会发现其实难度还可以。只要多思考下，建议先看一遍视频，就能把思路理顺。
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex){if (path.size() == k) {result.push_back(path);return;}//满足条件,returnfor(int i=startIndex;i<=n - (k - path.size()) + 1;i++){path.push_back(i);backtracking(n, k, i + 1); //继续递归path.pop_back();//回溯 }
}vector<vector<int>> combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};
216. 组合总和 III
如果把组合问题理解了，本题就容易一些了。
- 题目链接/文章讲解
- 视频讲解
这题要求只使用数字1到9, 每个数字 最多使用一次,那么这题本质上就和上面一题没有本质上区别.我用了一个gap来判断是不是满足条件,每往数组里加一个数 ,就重新计算下目标值差距. 注意,gap也要回溯, 进行先加后减处理
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
int gap=0;
void backtracking(int n, int k, int startIndex){ if (path.size() == k&&gap==0) {result.push_back(path);return;}//满足条件,returnif(gap<0||path.size() == k)return;//没找到，不满足条件,也returnfor(int i=startIndex;i<=9;i++){path.push_back(i);gap-=i;backtracking(n, k, i + 1); //继续递归path.pop_back();//回溯 gap+=i;//sum也要回溯}
}vector<vector<int>> combinationSum3(int k, int n) {result.clear(); // 可以不写path.clear(); // 可以不写sum=n;backtracking(n, k, 1);return result;}
};
17. 电话号码的字母组合
本题刚开始做会有点难度，建议先自己思考 20 分钟，没思路就直接看题解。
letterMap 是一个常量字符串数组，用于将数字映射到字母。例如，数字 2 对应 “abc”，数字 7 对应 “pqrs”。
终止条件: 如果当前组合的长度 s.size() 达到了输入数字字符串 digits 的长度，表示已经生成了一个完整的组合，将其加入 result 中。
循环部分: 对于当前数字 digits[num]，通过 letterMap[digits[num] - ‘0’] 获取对应的字母集，然后逐个将字母添加到组合字符串 s 中，递归调用 backtracking 来继续生成下一个字母，直到找到完整的组合。
回溯: 每次递归完成后，调用 s.pop_back() 来撤销上一步的选择，进入下一个字母的递归。
class Solution {
public:
const string letterMap[10] = {" ", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9
};vector<string> result;string s;void backtracking(string digits, int num){if(s.size()==digits.size()){result.push_back(s);return;}for (char ch :letterMap[digits[num]-'0']) {s.push_back(ch);backtracking(digits,num+1);s.pop_back();}
}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) {return result;}backtracking(digits, 0);return result;}
};
- 题目链接/文章讲解
- 视频讲解
确实,刚开始学回溯算法,有点头疼,但是当自己逐渐学懂了,其实难度也还行,本质上和递归一样,暴力穷举,不断试错,撤回,再试错. 一点点加油进步呢.