代码随想录算法训练营第二十五天 | 216.组合总和III、 17.电话号码的字母组合

216.组合总和III

题目链接：216.组合总和III

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

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

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

文章讲解/视频讲解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html

思路

首先确定回溯的函数参数，参数包括当前的组合path，当前遍历到的数字cur，组合的目标大小k，以及当前组合的总和与目标数字n的差值left。

什么时候回溯结束？当然是当前组合path的大小等于k的时候，这时判断一下left是否等于0，如果等于0则把当前path添加到结果中。

如何遍历？在当前的回溯中，依次从cur往后遍历，如果遍历的数i大于left或者大于9则停止。同时，递归地对添加的下一个数进行处理，此时的left值为left - i。

这里有一个要注意的点，数字只能在1到9之间。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> path;
        backtracking(path, 1, k, n);
        return results;
    }

    void backtracking(vector<int>& path, int cur, int k, int left){
        if(path.size() == k){
            if(left == 0) results.push_back(path);
            return;
        }
        for(int i = cur;i<=left && i<=9;i++){
            path.push_back(i);
            backtracking(path, i + 1, k, left - i);
            path.pop_back();
        }
    }
};

17.电话号码的字母组合

题目链接：17.电话号码的字母组合

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

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

文章讲解/视频讲解：https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html

思路

采用回溯来解决该问题，首先分析一下这道题的回溯架构。回溯分为横向和纵向两个方向的搜索，对于这道题来说，横向就是对当前数字i对应的字母映射的搜索，纵向则是对于输入的数字字符串的搜索。

依然按照回溯的三部曲进行分析。

回溯的函数参数？参数应该包括当前的字母组合path，当前遍历到的数字字符串下标cur，以及对于数字字符串digits的引用。

回溯什么时候结束？当数字字符串下标cur等于digits的长度的时候，表示已经遍历到了digits字符串的末尾。

如何进行遍历？在横向搜索过程中，依次遍历当前数字对应的字母列表，在每一次的遍历过程中，递归地对cur + 1的数字字符串下标进行纵向搜索。

C++实现

class Solution {
public:
    vector<string> results;
    vector<string> digitMaps;

    vector<string> letterCombinations(string digits) {
        digitMaps = {"0", "0", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string path;
        backtracking(path, 0, digits);
        return results;
    }

    void backtracking(string& path, int cur, const string& digits){
        if(cur == digits.size()){
            if(path != "") results.push_back(path);
            return;
        }
        int num = digits[cur] - '0';
        for(int i = 0;i<digitMaps[num].size();i++){
            path.push_back(digitMaps[num][i]);
            backtracking(path, cur + 1, digits);
            path.pop_back();
        }
    }
};