一、216.组合总和III
题目链接/文章讲解/视频讲解： https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html状态：已解决
1.思路
做过77题（上篇博客）后，这道题也就不难了，无非是多加了一个条件：组合之和等于n，只需要将这个加到终止条件那里即可。但这道题也有简化的地方，就是明确了每个样例的整个集合已经是固定的[1,...,9]。做过77就明白此题的做题套路了。
直接套模板：
（1）返回值为空，参数需要有：每层递归for循环的开始值m（组合无序，若每层递归for循环都是1~9，那么会出现{1，3}和{3，1}这种相同的组合方式）、前面递归所选值的累加和sum、n、k。
void backtracking(int m,int k,int n,int sum)（2）终止条件：vec.size() == k（vec是存放一条路径的变量），sum==n。
if(vec.size() == k){
if(sum==n)
result.push_back(vec);
return ;//一定要return
}（3）单层递归逻辑：for循环m~9，i的值放入vec中，sum加上i，开始子递归，然后再将i弹出。
for(int i=m;i<=9;i++){
vec.push_back(i);
backtracking(i+1,k,n,sum+i);
vec.pop_back();
}2.完整代码
class Solution {
public:
vector<int> vec;
vector<vector<int>> result;
void backtracking(int m,int k,int n,int sum){
if(vec.size() == k){
if(sum==n)
result.push_back(vec);
return ;
}
for(int i=m;i<=9;i++){
vec.push_back(i);
backtracking(i+1,k,n,sum+i);
vec.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vec.clear();
result.clear();
backtracking(1,k,n,0);
return result;
}
};另外，还可以减枝：当sum>n时，也终止。（for循环终止条件也可以为 i<9-(k-vec.size())+1 ，跟vec.size()==k终止差不多，故未添加。）
class Solution {
public:
vector<int> vec;
vector<vector<int>> result;
void backtracking(int m,int k,int n,int sum){
if(sum > n) return;
if(vec.size() == k){
if(sum==n)
result.push_back(vec);
return ;
}
for(int i=m;i<=9;i++){
vec.push_back(i);
backtracking(i+1,k,n,sum+i);
vec.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vec.clear();
result.clear();
backtracking(1,k,n,0);
return result;
}
};二、LeetCode77.组合
题目链接/文章讲解/视频讲解： https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html状态：已解决
1.思路
首先，这里有一段对应关系，每个数字对应几个字符。因此，我们第一步需要先存一个对应的字典。（这里可以用字符串数组存，也可以用vector<string>存，当然也可以用map做映射）
map<string,string> dic;
Solution() {
dic["2"] = "abc";
dic["3"] = "def";
dic["4"] = "ghi";
dic["5"] = "jkl";
dic["6"] = "mno";
dic["7"] = "pqrs";
dic["8"] = "tuv";
dic["9"] = "wxyz";
}做完这步后面回溯三部曲就跟前面的差不多了。
（1）返回值为空，参数需要有：目前遍历到digits的位置k、目前选择路径path、digits。
void backtracking(string digits, int k, string path)（2）终止条件digits.size() == k，sum==n。
if(digits.size() == k){
result.push_back(path);
return ;
}（3）单层递归逻辑：根据k得出当前位置的数字，根据字典得到该数字对应的字符串，然后用for循环选择的字符加入现有路径中。
string s = dic[digits.substr(k, 1)];
for(int i=0; i<s.size(); i++){
backtracking(digits, k+1, path + s[i]);
}2.完整代码
class Solution {
public:
map<string,string> dic;
vector<string> result;
Solution() {
dic["2"] = "abc";
dic["3"] = "def";
dic["4"] = "ghi";
dic["5"] = "jkl";
dic["6"] = "mno";
dic["7"] = "pqrs";
dic["8"] = "tuv";
dic["9"] = "wxyz";
}
void backtracking(string digits, int k, string path){
if(digits.size() == k){
result.push_back(path);
return ;
}
string s = dic[digits.substr(k, 1)];
for(int i=0; i<s.size(); i++){
backtracking(digits, k+1, path + s[i]);
}
}
vector<string> letterCombinations(string digits) {
result.clear();
if(digits.size() == 0) {
return result;
}
backtracking(digits, 0, "");
return result;
}
};
