回溯法
跟着一个很厉害的**博主(代码随想录)**的文章进行总结。
回溯本质上还是遍历搜索，可以用于解决组合、分割、子集、排列、棋盘问题等等，里面有一句总结的非常到位：
for表示横向搜索，递归表示纵向搜索；
组合问题
力扣77
典型的组合问题，可以采用典型的解决方法；思路就是，固定一位，然后在余下的里面固定另一位；
记录一下这里的一个错误，就是在最后退出的时候，最开始没有想清楚，手动clear了ans，导致了越界错误；因为我们是首先挑选一位放到ans，然后在余下的数里面挑选另一位，放到ans里面；当ans的size==k的时候，就可以添加答案然后返回；这一步之后，会进行“回”的操作，也就是撤销改变，因此，ans是不需要手动去clear的；
然后，这里可以进行一点优化，也就是剪枝操作，当i的后面没有k位数的时候，不用遍历；
也就是修改：
//for(int i=index;i<=n;i++)
for(int i=index;i<=n-(k-ans.size())+1;i++)
class Solution {
private:
vector<int> ans;
vector<vector<int>> ret;
void backTrace(int n,int k,int index)
{
//边界
if(k==ans.size())
{
ret.push_back(ans);
//ans.clear();//注意，回溯的时候，会自动将改变修正，所以不用人为的释放内存
return;
}
//执行
for(int i=index;i<=n;i++)
{
ans.push_back(i);
backTrace(n,k,i+1);
ans.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
/* 组合问题，回溯法解决，for表示横向搜索，递归表示纵向搜索；本质上还是穷举，但是根据实际问题可以添加剪枝操作 */
ans.clear();
ret.clear();
backTrace(n,k,1);
return ret;
}
};
力扣17
本题是求电话号码的字母组合，究其本质，仍然是组合问题，仍然可以采用回溯法遍历得出最终的答案；
首先应该分析出树的宽度和深度；数的宽度应该是数字对应的字符个数，深度是数字的个数；然后我们应该采用一个容器存储数字-字符串的组合，很容易想到哈希map
然后就是执行，每一次都得到当前位数字对应的字符串，然后for循环，添加，执行，回溯。
接着是边界，当到达了最后一位数字的时候开始返回，我们可以用index来表示输入digits的下标，当index==digits.size()的时候，将当前path答案添加到最终答案，然后return；
class Solution {
private:
vector<string> ans;
string path;//string需要初始化吗
unordered_map<char,string> dp=
{
{
'2',"abc"},
{
'3',"def"},
{
'4',"ghi"},
{
'5',"jkl"},
{
'6',"mno"},
{
'7',"pqrs"},
{
'8',"tuv"},
{
'9',"wxyz"}
};
void backTrace(string& digits,int index)
{
//边界
if(index==digits.size())
{
ans.push_back(path);
return;
}
//执行
string num=dp[digits[index]];
for(auto ch:num)
{
path.push_back(ch);
backTrace(digits,index+1);
path.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
if(0==digits.size())
return {
};
backTrace(digits,0);
return ans;
}
};
力扣39
在无重复元素数组里面，找出数字和为target的组合；还是一样分析横向搜索范围和纵向搜索范围。
横向for搜索范围是数组的长度，并且，每次往下继续搜索的时候，由于元素是可以重复使用的，因此，下标不用加一（当前元素及之后的元素可以继续使用），那么有一个疑问，为什么不直接从下标0开始呢，因为，最终答案里面的组合不能重复，如果每一层都是从下标0开始，那么，最终一定会有重复的组合
纵向搜索范围由数据的和来定，当数据和超过了target，就可以return，结束往下的搜索；
class Solution {
private:
vector<vector<int>> ans;
vector<int> path;
int sumPath=0;
void backTrace(vector<int>& candidates, int target,int index)
{
//边界
if(sumPath>target)
return;
else if(sumPath==target)
{
ans.push_back(path);
return;
}
//执行
for(int i=index;i<candidates.size();++i)
{
path.push_back(candidates[i]);
sumPath+=candidates[i];
backTrace(candidates,target,i);
sumPath-=candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backTrace(candidates,target,0);
return ans;
}
};
力扣40
这一题是上一题的进阶，数组里面存在重复的元素，但是最终的组合中，仍然不能有重复的组合，从而也就要求每一个元素只能使用一次；例如：[1,1,2]，target=3；按照上面的方法，最终的答案是[1,2]、[1,2]，这是不符合题意的，我们就是要通过某种方法去重；
一种简单的思想就是，当candidates[i]==candidates[i-1] ,就认为重复，但是这样，会导致，在单次组合中，原本存在的两个或多个相同的数据不能同时使用；
candidates[i]==candidates[i-1];
因此，我们需要改进，当前面一次彻底结束的时候，我们将used[i-1]置为false，表示不能再使用值等于candidates[i-1]的元素；
candidates[i]==candidates[i-1]&& used[i-1];
但是，这样仍然会导致一个问题，比如：[1,1,1,3,3,5],target=8；在得到答案[1,1,1,5]之后，由于在之前的尝试中，used[3]、used[4]已经置为false了，因此在后续的答案中，3不能够被连续使用了，就没有了[1,1,3,3]这个答案；
#include<bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<vector<int>> ans;
vector<int> path;
vector<bool> used;
void backTrace(vector<int>& candidates, int target,int index)
{
if(target<0)
return;
if(target==0)
{
ans.push_back(path);
return;
}
for(int i=index;i<candidates.size()&&(target-candidates[i])>=0;++i)
{
if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)
{
used[i]=false;
continue;//为什么需要添加used
}
target-=candidates[i];
path.push_back(candidates[i]);
//used[i]=true;
backTrace(candidates,target,i+1);
used[i]=false;
path.pop_back();
target+=candidates[i];
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
/* 每个数字在每个组合中只能使用一次； 解集不能包含重复的组合；candidates=[10,1,2,7,6,1,5],target=7; 按照之前的写法，答案中一定会有[1,6]、[6,1];因为之前处理的数据里面没有重复的元素； */
sort(candidates.begin(),candidates.end());
used.assign(candidates.size(),true);
backTrace(candidates,target,0);
return ans;
}
};
int main()
{
vector<int> candidates={
3,1,3,5,1,1};
int target=8;
Solution A;
vector<vector<int>>&& ans=A.combinationSum2(candidates,target);
return 0;
}
因此，我们需要在深度搜索的时候，保证相同元素值的可重复使用，以及在广度搜索时，相同元素值不可重复使用；也就是该博主说的，对于相同元素值的元素，保证在树层上的不可重复和树枝上的可重复
我们只需要将之前的去重稍作修改；
初始值是false，表示不可用，用于保证树层上元素值的不重复；
当我们进入了某一条路径下，将使用过的元素值对应的位置置为true，用于保证树枝上元素值的可重复使用
#include<bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<vector<int>> ans;
vector<int> path;
vector<bool> used;
void backTrace(vector<int>& candidates, int target,int index)
{
if(target<0)
return;
if(target==0)
{
ans.push_back(path);
return;
}
for(int i=index;i<candidates.size()&&(target-candidates[i])>=0;++i)
{
if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)
{
//used[i]=false;
continue;//为什么需要添加used
}
target-=candidates[i];
path.push_back(candidates[i]);
used[i]=true;
backTrace(candidates,target,i+1);
used[i]=false;
path.pop_back();
target+=candidates[i];
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
/* 每个数字在每个组合中只能使用一次； 解集不能包含重复的组合；candidates=[10,1,2,7,6,1,5],target=7; 按照之前的写法，答案中一定会有[1,6]、[6,1];因为之前处理的数据里面没有重复的元素； */
sort(candidates.begin(),candidates.end());
used.assign(candidates.size(),false);
backTrace(candidates,target,0);
return ans;
}
};
int main()
{
vector<int> candidates={
3,1,3,5,1,1};
int target=8;
Solution A;
vector<vector<int>>&& ans=A.combinationSum2(candidates,target);
return 0;
}
小结
从本周开始，跟着这个博主进行总结复习，终于将剑指offer做完了，力扣也做完了200道题目，方法、数据结构都有了一个初步的了解，接下来就是巩固和提高了；
回溯法，是递归的副产品；同时回溯这个问题模型是树，本质是遍历，for表示横向搜索，递归表示纵向搜索，在此基础上，可以添加剪枝操作来降低时间复杂度，其实也挺简单的，复杂的问题只是在简单的基础上，套了一层又一层小问题，例如上面的数字对应字符串的解决方式，同一树层，相同元素值的去重，以及后续的八皇后里面，如何判断皇后之间不会互相伤害。
京公网安备 11010502036488号