216.组合总和III
1.有了昨天做77.组合的经验，这题也是一样的思路，无非是多了个判断条件组合总和是否=n。（for循环内已经做了初步剪枝）
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int startIndex){
if(path.size()==k){
int sum=0;
for(int i=0;i<k;i++){
sum+=path[i];
}
if(sum==n){//判断组合总和是否=n
result.push_back(path);
return;
}
else return;
}
for(int i=startIndex;i<=10-(k-path.size());i++){
path.push_back(i);//处理结点
backtracking(n,k,i+1);//递归
path.pop_back();//回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n,k,1);
return result;
}
};2.这题我们还有一个更进一步的剪枝思路，因为我们循环时i是逐渐增大的。所以，当某一刻我们发现组合之和已经>n时，说明后面的组合之和也一定>n不满足条件了，就不用继续递归了，直接结束递归返回。
class Solution {
private:
int sum=0;
vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int startIndex){
if(sum>n) return;//剪枝
if(path.size()==k){
if(sum==n){//判断组合总和是否=n
result.push_back(path);
return;
}
else return;
}
for(int i=startIndex;i<=10-(k-path.size());i++){
sum+=i;
path.push_back(i);//处理结点
backtracking(n,k,i+1);//递归
path.pop_back();//回溯
sum-=i;
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n,k,1);
return result;
}
};17.电话号码的字母组合
1.其实本题的回溯部分倒不是很难理解，反而是电话数字与字母之间的映射关系不容易想到。
class Solution {
private:
string letterMap[10]={//二维数组映射数字与字母的关系
"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};
string path;
vector<string> result;
void backtracking(string str,int size,int index){
if(path.size()==size){
result.push_back(path);//把组合结果加入返回数组
return;
}
int digit=str[index]-'0';//把字符串中数字转化为整型
string letter=letterMap[digit];//根据映射关系，找出数字对应的字符串
for(int i=0;i<letter.size();i++){//遍历字符串枚举组合
path.push_back(letter[i]);
backtracking(str,size,index+1);//递归处理后面数字对应的字符串
path.pop_back();//回溯
}
}
public:
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return result;//空字符串特殊处理
backtracking(digits,digits.size(),0);
return result;
}
};今日总结：她总是只留下电话号码~
