组合总和III
题目：找出所有相加之和为n的k个数的组合。组合中只允许含有1-9的正整数，并且每种组合中不存在重复的数字。
组合变量个数为k个，和为n。简单思路是使用k重循环，一层层找出来，然后把每一层的数相加，等于n就把这个组合找出来，输出。但是n重……无从满足，就要想到用回溯暴力。
组合不强调顺序，元素重复的组合看作一个。
组合内元素不重复。
画树，k是深度，n是宽度。
class Solution{
private:
vector<vector<int>>result;//存放结果集
vector<int>path;//符合条件的结果
void backtracking(int targetSum, int k, int sum, int startIndex){
if(path.size() == k){
if(sum == targetSum)result.push_back(path);
return;
}
for(int i = startIndex; i <= 9; i++){
sum += i;//处理
path.push_back(i);//处理
backtracking(targetSum, k, sum, i + 1);
sum -= i;//回溯
path.pop_back();//回溯
}
}
public:
vector<vector<int>>combinationSum3(int k,int n){
result.clear();//可以不加
path.clear();
backtracking(n, k, 0, 1);
return result;
}
};剪去元素总和超过和n的，剪枝的地方可以放在递归函数开始的地方，
if(sum > targetSum){//剪枝操作
return;
}或者把剪枝放在调用递归之前，但是要记得先回溯。
for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){//剪枝
sum += i;//处理
path.push_back(i);//处理
if(sum > targetSum){//剪枝
sum -= i;//回溯
path.pop_back();//回溯
return;
}
backtracking(targetSum, k, sum, i + 1);//注意i+1调整startIndex
sum -= i;//回溯
path.pop_back();//回溯
}定义一维数组path
二维数组，放结果集
确定递归函数返回值，确定终止条件,确定单层搜索的逻辑
class Solution{
private:
vector<vector<int>>result;
vector<int>path;
void backtracking(int targetSum, int k, int sum, int startIndex){
if(sum > targetSum){
return;
}
if(path.size() == k){
if(sum == targetSum)result.push_back(path);
return;
}
for(int i = startIndex; i <= 9 - (k - path.size()) + 1;i++){
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.pop_back();
}
}
public:
vector<vector<int>>combinationSum3(int k. int n){
result.clear();
path.clear();
backtracking(n, k, 0, 1);
return result;
}
};电话号码
题目：
数字2——9，对应字母如上，输入两个数字，找出所有可能字母组合。
思路：
1.用map或定义一个二维数组，进行数字和字母之间的映射。
2.一个组合有两个字母，用双层for循环……n重for循环，用回溯算法
3.输入其他键（2-9以外）的异常情况
回溯>>
横向由for循环控制，纵向深度用递归控制.
回溯三部曲：
1.回溯函数参数，题目给定的string digits,int 型的index记录遍历到第几个数字了，就是用来遍历digits的（digits题目给定的数字字符串），同时index也表示树的深度。
vector<string>result;
string s;
void backtracking(const string& digits,int index)2.确定终止条件
如果index等于输入的数字个数（digits.size）,举例输入的“23”，深度就2，每次递归，遍历两次就可以。
if(index == digits.size()){
result.push_back(s);
return;
}3.确定单层遍历的逻辑
首先要取index指向的数字，找到对应的字符集。
然后for循环处理
int digit = digits[index]-'0';//将index对应的数字转化为int型
string letters = letterMap[digit];//取数字对应的字符集
for(int i = 0;i < letters.size();i++){
s.push_back(letters[i]);//处理，将i对应的字符添加到s末尾
backtracking(digits,index + 1);//递归，注意index+1,进入下一层，处理下一个数字
s.pop_back();//回溯
}
完整：
class Solution {
private:
const string letterMap[10] = {//用MAP定义一个二维数组，用来做映射
"",//0
"",//1
"abc",//2
"def",//3
"ghi",//4
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"//9
};
public:
vector<string>result;
string s;
void backtracking(const string& digits, int index){
if(index == digits.size()){//终止条件，一层递归结束
result.push_back(s);//收集结果
return;
}
int digit = digits[index] - '0';//将index指向的数字转化为int
string letters = letterMap[digit];//取数字对应的字符集
for(int i = 0; i < letters.size();i++){
s.push_back(letters[i]);//处理
backtracking(digits,index + 1);//递归，进入下一层，下一个数字的处理
s.pop_back();//回溯，释放掉放进去的字符
}
}
vector<string> letterCombinations(string digits) {
s.clear();
result.clear();
if(digits.size()== 0){
return result;
}
backtracking(digits,0);
return result;
}
};
