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

77. 组合

• 题目链接：77. 组合
• 思路：回溯算法，倒着选择1~n中的数，倒着选择的特殊性在于，选择的数就是剩下的可选择的数的数量，所以每次选择的数要比剩下需要选择的数的数量多才行
• 代码：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;
        auto dfs = [&](auto&& dfs, int i) {
            int d = k - path.size(); // 还需要选择的数的数量
            if(d == 0) { // 成功
                ans.push_back(path); 
                return;
            }
			
			// 倒着选择的特殊性，选择的数要比剩下需要选择的数量大
            for(int j = i; j >= d; j--) { 
                path.push_back(j);
                dfs(dfs, j - 1);
                path.pop_back();
            }
    
        };
        dfs(dfs, n); // 从n开始选择
        return ans;
    }
};

216.组合总和III

• 题目链接：216.组合总和III
• 思路：
  1. 同上一道组合题一样的思路，不过这里需要和为n，选择的数在[1, 9]之间，仍然是倒着选，当选择的数量为k，并且和为n时，即为符合答案；
  2. 剪枝优化，这里剪枝优化的关键点在于，剩下还需要选d个数，倒着选，剩下选择的数的范围是[1, i]，如果 i + (i - 1) + (i - 2)… + (i - d + 1) = (2 * i - d + 1) / 2，等差数列和公式，即最大的d个数，的和加起来都没有，再加上之前选择的数的值的和都达不到目标值，就可以不继续往下递归；
• 代码：

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        auto dfs = [&](auto&& dfs, int i, int t) {
            int d = k - path.size(); // 还要选 d 个数
            if (t < 0 || t > (i * 2 - d + 1) * d / 2) { // 剪枝优化
                return;
            }
            // 这是t 只能是 >= 0, d >= 0
            if (d == 0) { // 找到一个合法组合
                ans.emplace_back(path);
                return;
            }
            for (int j = i; j >= d; j--) {
                path.push_back(j);
                dfs(dfs, j - 1, t - j);
                path.pop_back();
            }
        };
        dfs(dfs, 9, n);
        return ans;
    }
};

17.电话号码的字母组合

• 题目链接：17.电话号码的字母组合
• 思路：
  1. 这道题思路依然和组合差不多，仍然是选择，不过这里根据数去选择对应的字符，所以需要有一个数和字符的对应表，先用map创建对应的数和字符对应表；
  2. 每次根据digits，对应位置中的数字，选择这个数字对应的字符集中的一个，满足情况加入到结果列表即可
• 代码：

class Solution {
public:
    
    vector<string> letterCombinations(string digits) {
        unordered_map<int, string> kv = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}}; // 创建对应表
        vector<string> ans;
        if(digits.empty()) // 字符串为空没有情况
            return ans;
        string tmp;
        int n = digits.length(); // 选择的长度
        auto dfs = [&](auto&& dfs, int i) {
            if(i == n) { // 长度为n，加入到结果中
                ans.push_back(tmp);
                return;
            }
            for(char c : kv[digits[i] - '0']) { // 每次选择数字对应字符集中的一个
                tmp.push_back(c);
                dfs(dfs, i+1);
                tmp.pop_back();
            }
        };
        dfs(dfs, 0); // 从第一个开始
        return ans;
    }
};