代码随想录算法训练营Day22 | Leetcode 77. 组合 | 216.组合总和III | 17.电话号码的字母组合

今日任务

77. 组合

• 题目链接： https://leetcode.cn/problems/combinations/description/
• 题目描述：
  

Code

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    vector<vector<int>> combine(int n, int k) {
        // int startIdx = 1;
        // path.reserve(n);
        // int size = 1;
        // for(int i = 0; i < k; i++){
        //     size *= (n - i);
        //     size /= (i + 1);
        // }
        // rst.reserve(size);
        // backtracing(n, k, startIdx);
        // return rst;

        // 枚举选哪个
        // function<void(int)> dfs = [&](int i)->void{
        //     int d = k - path.size();
        //     if(d == 0){
        //         ans.emplace_back(path);
        //         return;
        //     }
        //     for(int j = i; j >= d; j--){
        //         path.push_back(j);
        //         dfs(j - 1);
        //         path.pop_back();
        //     }
        // };

        // 选或不选
        function<void(int)> dfs = [&](int i)->void{
            int d = k - path.size();
            if(d == 0){
                ans.emplace_back(path);
                return;
            }
            // i > d 可以不选i
            if(i > d){
                dfs(i - 1);
            }
            // 选i
            path.push_back(i);
            dfs(i - 1);
            path.pop_back();// 恢复现场
        };
        dfs(n);
        return ans;

    }

    // void backtracing(int n, int k, int startIdx){
    //     // if(path.size() + (n - startIdx + 1) < k){
    //     //     return ;
    //     // }
    //     if(path.size() == k){
    //         rst.emplace_back(path);
    //         return;
    //     }
    //     for(int i = startIdx; i <= n - (k - path.size() - 1); i++){
    //         path.emplace_back(i);
    //         backtracing(n, k, i + 1);
    //         path.pop_back();
    //     }
    // }

};

216. 组合总和 III

• 题目链接： https://leetcode.cn/problems/combination-sum-iii/description/
• 题目描述：
  

Code

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        // int startNum = 1;
        // int sum = 0;
        // backtracing(n, k, startNum, sum);
        // return rst;

        // function<void(int, int)> dfs = [&](int i, int t)->void{
        //     int d = k - path.size();
            
        //     if(t < 0 || t > (i * 2 - d + 1) * d / 2){
        //         return;
        //     }

        //     if(d == 0){
        //         ans.emplace_back(path);
        //         return;
        //     }
        //     if(d < 0){
        //         return;
        //     }
        //     for(int j = i; j >= d; j--){
        //         path.push_back(j);
        //         dfs(j - 1, t - j);
        //         path.pop_back();
        //     }
        // };

        function<void(int, int)> dfs = [&](int i, int t)->void{
            int d = k - path.size();
            if(t < 0 || t > (2 * i - d + 1) * d / 2){
                return;
            }
            if(d == 0){
                ans.emplace_back(path);
                return;
            }
            if(i > d){
                dfs(i - 1, t);
            }

            path.push_back(i);
            dfs(i - 1, t - i);
            path.pop_back();
        };

        dfs(9, n);
        return ans;
    }
    // void backtracing(int n, int k, int startNum, int sum){
    //     if(group.size() == k && sum == n){
    //         rst.emplace_back(group);
    //         return ;
    //     }

    //     for(int i = startNum; i <= 9 - (k - group.size()) + 1; i++){
    //         group.emplace_back(i);
    //         sum += i;
    //         if(sum > n){
    //             sum -= i;
    //             group.pop_back();
    //             return;
    //         }
    //         backtracing(n, k, i + 1, sum);
    //         sum -= i;
    //         group.pop_back();
    //     }

    // }
};

17. 电话号码的字母组合

• 题目链接： https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
• 题目描述：
  

Code

class Solution {
    string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        int n = digits.size();
        if(n == 0){
            return ans;
        }
        string path(n, 0);
        function<void(int)> dfs = [&](int i)->void{
            if(i == n){
                ans.emplace_back(path);
                return;
            }
            for(char c : MAPPING[digits[i] - '0']){
                path[i] = c;
                dfs(i + 1);
            }
        };
        dfs(0);
        return ans;
    }
};