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

Day18 OK，继续追今天的打卡！第十八天

以下是今日份的总结
- - 如何理解回溯法
- 组合
- 组合总和III
- 电话号码的字母组合

以下是今日份的总结

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开始，所以<=n
            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;
    }

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;
        }

        // 遍历
        //外层遍历digits
        for (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;
    }