代码随想录算法训练营第二十一天| 回溯 216. 组合总和 III 17. 电话号码的字母组合

216. 组合总和 III

可以参考77.组合中关于选取数组的相关操作。

递归函数的返回值以及参数：一般为void类型

递归函数终止条件：path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，然后当n为0的时候（找到数组值为n），终止，将结果导入res中

递归函数单层逻辑：回溯法的搜索过程就是一个树型结构的遍历过程，for循环用来横向遍历，递归的过程是纵向遍历。

class Solution {
public:vector<vector<int>>res;void backtracing(vector<int>path,int k,int n,int index){if(path.size()==k&&!n){res.push_back(path);return;}for(int i=index;i<=9;i++){path.push_back(i);n-=i;backtracing(path,k,n,i+1);n+=i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {vector<int>path;int index=1;backtracing(path,k,n,index);return res;}
};

剪枝操作

如果n为负了，就没有再继续减下去的必要了，可以提前回溯。

 for(int i=index;i<=9-(k-path.size())+1;i++){path.push_back(i);n-=i;//提前回溯if(n<0){n+=i;path.pop_back();return;}backtracing(path,k,n,i+1);n+=i;path.pop_back();}

 完整代码：

class Solution {
public:vector<vector<int>>res;void backtracing(vector<int>path,int k,int n,int index){if(path.size()==k&&!n){res.push_back(path);return;}for(int i=index;i<=9-(k-path.size())+1;i++){path.push_back(i);n-=i;if(n<0){n+=i;path.pop_back();return;}backtracing(path,k,n,i+1);n+=i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {vector<int>path;int index=1;backtracing(path,k,n,index);return res;}
};

17. 电话号码的字母组合

遇到回溯的题目，首先可以尝试画一下n叉树

确定回溯函数参数：首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。

确定终止条件:到达叶子结点是搜索，即stringg s的长度要与原先输入的长度相等

确定单层遍历逻辑：首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。然后for循环来处理这个字符集。

class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string> res;string s;void backtracing(string digits,int index){if(index==digits.size()){res.push_back(s);return;}int num=digits[index]-'0';string letter=letterMap[num];for(int i=0;i<letter.size();i++){s.push_back(letter[i]);backtracing(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {int index=0;if(!digits.size()) return res;backtracing(digits,index);return res;}
};