回溯算法集合
文章目录
- 回溯算法集合
- [leetcode-39. 组合总和🌟🌟](https://leetcode-cn.com/problems/combination-sum/)
- [leetcode-17. 电话号码的字母组合🌟🌟](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
- [leetcode-46. 全排列🌟🌟](https://leetcode-cn.com/problems/permutations/)
- [leetcode-77. 组合🌟🌟](https://leetcode-cn.com/problems/combinations/)
- [leetcode-37. 解数独🌟🌟🌟](https://leetcode-cn.com/problems/sudoku-solver/)
回溯算法也有很多题目，全排列什么的，这些都是难者不会会者不难的题。
我一开始就一道也做不出来，后来就感觉其实还可以。也弄个记录，希望学有所得，练有所获。
回溯算法简介-个人理解
个人感觉，回溯法就是枚举加上剪枝，一般是要求出所有的组合，排列这种的，给你一个集合。让从里面取元素出来符合某一个目标。一个集合要是有n个元素，那么一共可能的组合数是很大的，这个不同的要求不同，比如有无顺序要求，可不可以重复取出等等，具体问题具体分析。但是大多数情况，我们暴力枚举的话肯定是时间复杂度太大了。
回溯呢就是我们在遍历的过程中，到了某一个位置，我们可以判断出是否到达目标，或者下面还有没有可能到达目标了。
如果是还有机会的话，就继续向下延伸，但是要是判断已经到头了，就及时止损，回退一步，换个方向探索。这样的话就可以避免很多不需要的搜索，提高解决问题的效率。
回溯法一般都是树状的搜索过程，而树结构天然就和递归结果非常的契合，所以回溯算法一般使用递归形式，好理解也好书写，但是具体问题如果有性能要求，到时看看能不能改写为迭代的，省内存。
leetcode-39. 组合总和🌟🌟
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
解题思路
这个问题是让求出可能的组合数，也不需要是什么连续子数组这种，算是比较好弄的。
代码实现
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>>vv; //用来存放最后的结果
vector<int>v;
dfs(candidates,target,v,vv);
return vv;
}
void dfs(vector<int>& candidates, int target,vector<int>&v,vector<vector<int>>&vv){
if(target<0)return;
if(target==0){ //判断出找到了一个可行的组合
vv.push_back(v);
return ;
}
for(int i=0;i<candidates.size();i++){
//
if(v.size()>0&&v.back()<=candidates[i]||v.size()==0){
v.push_back(candidates[i]); //满足条件 填入组合
dfs(candidates,target-candidates[i],v,vv); //在这个组合基础上进行递归，相当于到了一个新的分支
v.pop_back();//退一步去探寻其他分支
}
}
}
};
leetcode-17. 电话号码的字母组合🌟🌟
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zr1qS4ty-1652626890378)(/Users/autreyhepburn/Library/Application Support/typora-user-images/image-20211212234617933.png)]
解题思路
这就是列举可能的结果，我觉得回溯重要就是要想清楚到哪里要停，这题也是比较好想到的。看代码就懂了
代码实现
class Solution {
public:
string num[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> letterCombinations(string digits) {
//用来存放数字
vector<string> vs;//用来存放结果
int n=digits.size();
if(n==0)return vs;
string s="";//用来记录可行的结果
huishu(0,n,s,vs,digits);
return vs;
}
//k是用来记录当前取了几个数字 n是数字总数
void huishu(int k,int n,string &s,vector<string> &vs,string digits){
if(k==n){//取到n个数了可以返回了
vs.push_back(s);
}else{
//这是回溯的主要实现 用循环遍历所有可取的字符
for(int i=0;i<num[digits[k]-'0'].size();i++){
//先push 然后递归向下，递归结束再 pop相当于回退一步
s.push_back(num[digits[k]-'0'][i]);
huishu(k+1,n,s,vs,digits);
s.pop_back();
}
}
}
};
leetcode-46. 全排列🌟🌟
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
解题思路
这是最经典的一个回溯了吧，就是列出所有的可能，其实就是枚举，但是回溯的树形最适合这种枚举了，不用考虑重复情况。全排列不重复，要是组合的话要考虑重复了。
代码实现
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> vv;//用来存放结果
vector<int>v;//存放可行的排列
int n=nums.size();//排列的长度要知道
vector<int>visit(n,0); //这个是排列，排列里面不能有重复的
dfs(n,v,vv,nums,visit);
return vv;
}
void dfs(int n,vector<int>&v,vector<vector<int>> &vv,vector<int> nums,vector<int> &visit){
if(v.size()==n){
vv.push_back(v);
}else{
for(int i=0;i<nums.size();i++){
if(visit[i]==0){
visit[i]=1;
v.push_back(nums[i]);
dfs(n,v,vv,nums,visit);
v.pop_back();
visit[i]=0;
}
}
}
}
};
leetcode-77. 组合🌟🌟
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
解题思路
排列完就是组合了，就是不能考虑顺序了，那就从前往后就可以了，就是控制好只能取1，3不能取3，1就好了。
代码实现
在排列的基础上小改一下,首先这个是从前往后取的，所以不存在返回去，就不需要visit数组了，其次这个可以减枝，就是要是剩下没有访问到的加上当前的还不够k，那就没必要往下走了
class Solution {
public:
vector<vector<int>> combine(int n,int k) {
vector<vector<int>> vv;//用来存放结果
vector<int>v;//存放可行的组合
dfs(n,k,1,v,vv);
return vv;
}
void dfs(int n,int k,int m,vector<int>&v,vector<vector<int>> &vv){
//回溯需要减枝啊还是
if (v.size() + (n - m + 1) < k) {
return;
}
if(v.size()==k){
vv.push_back(v);
}else{
for(int i=m;i<=n;i++){
v.push_back(i);
dfs(n,k,i+1,v,vv);
v.pop_back();
}
}
}
};
leetcode-37. 解数独🌟🌟🌟
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
解题思路
这个的思路就是枚举加减枝啊，每次到了一个空的地方就得枚举这个地方可以填的数字，取出一个数字以后要判断他可不可以，如果可以的话就去处理下一空格，如果当前这一个分支是不可行的，就要回退
这个过程通常都是通过在递归前后改变状态完成的。
例如上图这个，dfs调用前设置为1，在调用后设置为0，代表回退。
这道题的给我的一个启发是，之后这种N*N处理空格的，可以吧空格的坐标用pair<int,int>坐记录，这样在处理过程中不需要再遍历了。这个我一开始没有想到。
这个处理的结尾就是判断所有需要处理的位置是否都进行了处理。
这行代码代码就是做这个工作的。回溯算法一般是有一个框架的，我们要想清楚该怎么忘框架里面填东西。
代码实现
class Solution {
public:
bool vr[9][9];
bool vc[9][9];
bool vb[3][3][9];
vector<pair<int,int>> mspace;
void solveSudoku(vector<vector<char>>& board) {
//要先初始化一下
memset(vr, false, sizeof(vr));
memset(vc, false, sizeof(vc));
memset(vb, false, sizeof(vb));
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
mspace.emplace_back(i, j);
}
else {
int digit = board[i][j] - '0' - 1;
vr[i][digit] = vc[j][digit] = vb[i / 3][j / 3][digit] = true;
}
}
}
dfs(0,board);
}
bool dfs(int index,vector<vector<char>>& board){
if(index==mspace.size())return true;
int m=mspace[index].first;
int n=mspace[index].second;
for(int i=0;i<9;i++){
if(vr[m][i]==false&&vc[n][i]==false&&vb[m/3][n/3][i]==false){
vr[m][i]=1;
vc[n][i]=1;
vb[m/3][n/3][i]=1;
board[m][n]='0'+i+1;
if(dfs(index+1,board)){
return true;
}
vr[m][i]=0;
vc[n][i]=0;
vb[m/3][n/3][i]=0;
}
}
return false;
}
};
