文章目录
Leetcode77
1.问题描述
2.解决方案
解法一：普通回溯
包含回溯三部曲，回溯模板等等要点，很重要！，俺的博客和代码sxl都说的很清楚就不多说了
class Solution {
public:
vector<vector<int> > ans;
vector<int> path;
void backtracking(int n,int k,int startIndex){
if(path.size()==k){
ans.push_back(path);
return;
}
for(int i=startIndex;i<=n;i++){
path.push_back(i);
backtracking(n,k,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n,k,1);
return ans;
}
};
解法二：剪枝回溯
和普通回溯就差了一个for的遍历条件，剪枝俺的博客和代码sxl都说的很清楚就不多说了
for(int i=startIndex;i<=n-(k-path.size())+1;i++)
class Solution1 {
public:
vector<vector<int> > ans;
vector<int> path;
void backtracking(int n,int k,int startIndex){
if(path.size()==k){
ans.push_back(path);
return;
}
for(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) {
backtracking(n,k,1);
return ans;
}
};
Leetcode216
1.问题描述
2.解决方案
首先分析本题和上一题77的区别
1.就是不仅要求k个数，还要求和为n，那说白了不就是加了一个和为n的条件嘛
2.当然随之而来，需要多两个参数，sum你需要记录目前为止path里的节点的和以便终止条件判断，n也就是targetsum目标和
3.其他的几乎一模一样还是回溯三部曲，回溯模板等步骤
void backtracking(int k,int n,int startIndex,int sum)
解法一：普通回溯
代码sxl有详细过程这就不多说了，就正常步骤，分析清楚和77的区别就好
class Solution {
public:
vector<vector<int> > ans;
vector<int> path;
void backtracking(int k,int n,int startIndex,int sum){
if(path.size()==k){
if(sum==n) ans.push_back(path);
return;
}
for(int i=startIndex;i<=9;i++){
sum+=i;
path.push_back(i);
backtracking(k,n,i+1,sum);
sum-=i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k,n,1,0);
return ans;
}
};
解法二：剪枝回溯
剪枝一：
if(sum>n) return;
剪枝二：
for(int i=startIndex;i<=9-(k-path.size())+1;i++)
class Solution1 {
public:
vector<vector<int> > ans;
vector<int> path;
void backtracking(int k,int n,int startIndex,int sum){
if(sum>n) return;
if(path.size()==k){
if(sum==n) ans.push_back(path);
return;
}
for(int i=startIndex;i<=9-(k-path.size())+1;i++){
sum+=i;
path.push_back(i);
backtracking(k,n,i+1,sum);
sum-=i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k,n,1,0);
return ans;
}
};
Leetcode17
1.问题描述
2.解决方案
解法一：显示回溯
a.对比17和77，216
这个题和上面两个题77，216都有所不同，上面两个题都是在遍历同一集合，所以在递归参数中出现startindex这个参数，也就是用来标记这一层从集合中的哪开始取数，而一开始我也准备加入这个参数，后来发现加了这个参数好像递归的时候根本不变这个参数的值，所以就删掉了，由于17是不同集合，所以没到新的一层都是从0开始遍历，所以也不需要什么startIndex来标记了！
void backtracking(string digits,int digitsIndex,int traverseStringIndex)
void backtracking(string digits,int digitsIndex)
b.string居然也能push_back()和pop_back()
c.两种终止条件都符合逻辑
if(path.size()==digits.size()){
ans.push_back(path);
return;
}
//if(digitsIndex==digits.size()){
// ans.push_back(path);
// return;
//}
d.数字和字母映射这个注意
const string letterMap[10]={
"", //0
"", //1
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz", //9
};
e.其他的就是常规回溯操作没什么区别和上面的题目
class Solution {
public:
const string letterMap[10]={
"", //0
"", //1
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz", //9
};
string path;
vector<string> ans;
void backtracking(string digits,int digitsIndex,int traverseStringIndex){
if(path.size()==digits.size()){
ans.push_back(path);
return;
}
//if(digitsIndex==digits.size()){
// ans.push_back(path);
// return;
//}
string traverseString=letterMap[digits[digitsIndex]-48];
for(int i=traverseStringIndex;i<traverseString.size();i++){
path=path+traverseString[i];
backtracking(digits,digitsIndex+1,traverseStringIndex);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return ans;
backtracking(digits,0,0);
return ans;
}
};
class Solution1 {
public:
const string letterMap[10]={
"", //0
"", //1
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz", //9
};
string path;
vector<string> ans;
void backtracking(string digits,int digitsIndex){
if(path.size()==digits.size()){
ans.push_back(path);
return;
}
//if(digitsIndex==digits.size()){
// ans.push_back(path);
// return;
//}
string traverseString=letterMap[digits[digitsIndex]-48];
for(int i=0;i<traverseString.size();i++){
path.push_back(traverseString[i]);
backtracking(digits,digitsIndex+1);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return ans;
backtracking(digits,0);
return ans;
}
};
解法二：隐式回溯
表面上看好像把path当作参数，这没有进行回溯操作一样，其实不然，递归中传入的是path+traverseString[i]，那么下一层递归函数中path改变了，然后这一层中其实path根本没变也就是说执行完backtracking(digits,digitsIndex+1,path+traverseString[i]); path根本就没变可以直接执行下一个for，所以也没有回溯这一说，但是可读性差！
for(int i=0;i<traverseString.size();i++){
//path.push_back(traverseString[i]);
backtracking(digits,digitsIndex+1,path+traverseString[i]);
//path.pop_back();
}
class Solution2 {
public:
const string letterMap[10]={
"", //0
"", //1
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz", //9
};
//vector<char> path;
//string path;
vector<string> ans;
void backtracking(string digits,int digitsIndex,string path){
if(path.size()==digits.size()){
ans.push_back(path);
return;
}
//if(digitsIndex==digits.size()){
// ans.push_back(path);
// return;
//}
string traverseString=letterMap[digits[digitsIndex]-48];
for(int i=0;i<traverseString.size();i++){
//path.push_back(traverseString[i]);
backtracking(digits,digitsIndex+1,path+traverseString[i]);
//path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return ans;
backtracking(digits,0,"");
return ans;
}
};