216.组合总和III
题目链接：216.组合总和III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
思路
首先确定回溯的函数参数，参数包括当前的组合path，当前遍历到的数字cur，组合的目标大小k，以及当前组合的总和与目标数字n的差值left。
什么时候回溯结束？当然是当前组合path的大小等于k的时候，这时判断一下left是否等于0，如果等于0则把当前path添加到结果中。
如何遍历？在当前的回溯中，依次从cur往后遍历，如果遍历的数i大于left或者大于9则停止。同时，递归地对添加的下一个数进行处理，此时的left值为left - i。
这里有一个要注意的点，数字只能在1到9之间。
C++实现
class Solution {
public:
vector<vector<int>> results;
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> path;
backtracking(path, 1, k, n);
return results;
}
void backtracking(vector<int>& path, int cur, int k, int left){
if(path.size() == k){
if(left == 0) results.push_back(path);
return;
}
for(int i = cur;i<=left && i<=9;i++){
path.push_back(i);
backtracking(path, i + 1, k, left - i);
path.pop_back();
}
}
};
17.电话号码的字母组合
题目链接：17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路
采用回溯来解决该问题，首先分析一下这道题的回溯架构。回溯分为横向和纵向两个方向的搜索，对于这道题来说，横向就是对当前数字i对应的字母映射的搜索，纵向则是对于输入的数字字符串的搜索。
依然按照回溯的三部曲进行分析。
回溯的函数参数？参数应该包括当前的字母组合path，当前遍历到的数字字符串下标cur，以及对于数字字符串digits的引用。
回溯什么时候结束？当数字字符串下标cur等于digits的长度的时候，表示已经遍历到了digits字符串的末尾。
如何进行遍历？在横向搜索过程中，依次遍历当前数字对应的字母列表，在每一次的遍历过程中，递归地对cur + 1的数字字符串下标进行纵向搜索。
C++实现
class Solution {
public:
vector<string> results;
vector<string> digitMaps;
vector<string> letterCombinations(string digits) {
digitMaps = {"0", "0", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string path;
backtracking(path, 0, digits);
return results;
}
void backtracking(string& path, int cur, const string& digits){
if(cur == digits.size()){
if(path != "") results.push_back(path);
return;
}
int num = digits[cur] - '0';
for(int i = 0;i<digitMaps[num].size();i++){
path.push_back(digitMaps[num][i]);
backtracking(path, cur + 1, digits);
path.pop_back();
}
}
};