leetcode_day24

今日任务：

• 77. 组合
• 216. 组合总和Ⅲ
• 17. 电话号码的字母组合

前言

进入回溯算法篇章，对递归掌握仍然不熟练，尤其是回溯算法，在左的课上写全排列等题目简直惨不忍睹，趁此机会，再次尝试学会回溯算法，每题务必隔天复习重写熟悉

卡哥的题解也要仔细看，综合多篇题解学习。

文章讲解：https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
视频讲解： https://www.bilibili.com/video/BV1cy4y167mM
代码随想录：https://programmercarl.com/

77. 组合

题目：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路：

多重for循环就行，但是由于层数不定，所以不能直接for，需要靠递归来实现任意层数循环

class Solution {
public:
    vector<vector<int>> ans;    //回溯模板1：总答案
    vector<int> temp;           //回溯模板2：单个答案暂存
    void backtracking(int n, int k, int start) {
        if(temp.size() == k) {  //回溯模板3：递归结束条件：遍历到叶子节点
            ans.push_back(temp);
            return ;
        }
        for(int i = start;i <= n - k + temp.size() + 1;i++) {
            temp.push_back(i);  //回溯模板4：选择当前，进入下一步
            backtracking(n, k, i + 1);
            temp.pop_back();    //回溯模板5：取消之前操作，回溯
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }
};

216. 组合总和Ⅲ

题目：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

思路：

和上一道题很像，卡哥选题还是很有深意的。熟悉模板写法，给出的代码没有剪枝，剪枝写法参见：

代码随想录 | 组合总和iii

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void backtracking(int k, int n, int start) {
        if(temp.size() == k) {
            if(n == 0) ans.push_back(temp);
            return;
        }
        for(int i = start;i <= 9;i++) {
            temp.push_back(i);
            backtracking(k, n - i, i + 1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return ans;
    }
};

17. 电话号码的字母组合

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路：

仍然是不定次数for循环，使用递归来解，同样，剪枝写法参见代码随想录 | 电话号码的字母组合

注意打表方式，值得学习，自己打表还用的unordered_map，结果打出来一堆bug，还是string数组聪明。

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