【代码随想录_Day18】77. 组合 216.组合总和III 17.电话号码的字母组合

以下是今日份的总结

77 组合
216 组合总和III
17 电话号码的字母组合

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

今天的题目难度不低，尽量还是写一些简洁代码 ^ _ ^

组合

思路：

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
n相当于树的宽度，k相当于树的深度。

值得注意的是

每次搜索到了叶子节点，我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

递归

    vector<vector<int>> result;vector<int> path;void backTrack(int n,int k, int start){//终止条件if(path.size()==k){result.push_back(path);return;}//开始遍历for(int i = start;i<=n;i++){//根据题意 i从1开始，所以<=npath.push_back(i);backTrack(n, k, i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {//判空if(k>n||k==0||n==0) return vector<vector<int>>();backTrack(n, k, 1);return result;}

for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了,优化如下：

    vector<vector<int>> result;vector<int> path;void backTrack(int n,int k, int start){//终止条件if(path.size()==k){result.push_back(path);return;}//开始遍历//i至多遍历到n-(k-path.size())+1，往后就没有意义了for(int i = start;i<=n-(k-path.size())+1;i++){path.push_back(i);backTrack(n, k, i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {//判空if(k>n||k==0||n==0) return vector<vector<int>>();backTrack(n, k, 1);return result;}

组合总和III

思路：

回溯法，和上一题思路一样，在回溯的过程中加入了总和的加减

值得注意的是

总和的加减分别对应了push和pop

递归

    int sum = 0;vector<vector<int>>res;vector<int>vec;void backTrack(int k, int n, int start){//终止条件if(sum == n&&vec.size()==k){res.push_back(vec);return;}//遍历for(int i = start; i<=9;i++){vec.push_back(i);sum+=i;//累加当前值，以便查找符合条件的数组backTrack(k, n, i+1);vec.pop_back();sum -= i; //回溯的时候把累加的值也减去}}vector<vector<int>> combinationSum3(int k, int n) {backTrack(k, n, 1);return res;}

电话号码的字母组合

思路：

回溯法，但是每层的分支是已知的，只需要按顺序遍历即可

值得注意的是

遍历string是char，char转int

递归

    vector<vector<char>> keyboard = {{},{'a', 'b', 'c'},      // 2{'d', 'e', 'f'},      // 3{'g', 'h', 'i'},      // 4{'j', 'k', 'l'},      // 5{'m', 'n', 'o'},      // 6{'p', 'q', 'r', 's'}, // 7{'t', 'u', 'v'},      // 8{'w', 'x', 'y', 'z'}  // 9};vector<string> res;string s;void backTrack(string str,int start) {if(str=="")return;// 终止条件if (str.size() == s.size()) {res.push_back(s);return;}// 遍历//外层遍历digitsfor (int i = start; i < str.size(); i++) {int num = str[i]-'0';//char转int//为了遍历对应按键的字母for (int j = 0; j < keyboard[num-1].size(); j++) {s.push_back(keyboard[num-1][j]);//末尾加上选择的字符backTrack(str,i+1);s.pop_back();//回溯，弹出string末尾的字符}}}vector<string> letterCombinations(string digits) {backTrack(digits,0);return res;}

写在最后

----OK，今日份的博客就写到这里，这一期的回溯法很巧秒啊，明天继续加油！！！
—看了看下期的题，但是我的栈还有一节没写；
–追上时间进度了吗？如追，从欠三天变成欠二天！！（笑
-今天不知道有没有。