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

216.组合总和III

代码随想录链接

题目

LeetCode-216.组合总和III

使用\([1, 9]\)范围内的k个正整数, 找出这k个正整数之和等于n的所有组合.

自己的想法

和昨天的题一样, 回溯套模板呗.

题解

class Solution {
private:
    vector<vector<int>> result;             // 记录符合条件的集合
    vector<int> current;                    // 记录回溯过程中的集合
    int sum = 0;                            // 记录集合之和
    void backtracing(int k, int n, int start) {
        if (current.size() == k) {          // 集合含有k个元素时, 判断之和是否满足条件
            if (sum == n) {
                result.push_back(current);
            }
            return;                         // 无论满不满足条件, 都进行回溯
        }

        for (int i = start + 1; i <= n - sum && i < 10; i++) {  // 横向遍历, 确定集合中下一个位置上填什么
            current.push_back(i);           // 推入集合下一个位置上的数
            sum += i;                       // 修改集合之和
            backtracing(k, n, i);           // 迭代来填充下下个位置
            current.pop_back();             // 回溯, 弹出下个位置的数字
            sum -= i;                       // 对应修改集合之和
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracing(k, n, 0);
        return result;
    }
};

17.电话号码的字母组合

代码随想录链接

题目

LeetCode-17.电话号码的字母组合

给定一个包含2-9的字符串, 返回其中能代表的所有字母组合, 2-9与字母的映射关系与功能机按键相同.暴露年龄

自己的想法

与上一题相似, 多加一些判断即可.

题解

class Solution {
private:
    vector<string> result;              // 符合条件的结果的集合
    string path = "";                   // 记录当前字符串
    const string letterMap[10] = {      // 记录键盘数字与字符的映射
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    void backtracing(string digits, int letterIndex) {
        if (path.size() == digits.size() && digits.size()) {    // 当前字符串与数字字符串等长且不为0时, 推入结果
            result.push_back(path);
            return;
        }
        if (letterIndex >= digits.size()) return;               // 防止下方遍历越界
        int currentDigits = digits[letterIndex] - '0';          // 取当前函数的数组, 并字符char转化为int
        for (int i = 0; i < letterMap[currentDigits].size(); i++) { // 横向遍历当前函数的数字可以代表的字符
            path += letterMap[currentDigits][i];                // 推入字符
            backtracing(digits, letterIndex + 1);               // 填充下一位置
            path.pop_back();                                    // 弹出字符, 进行下次循环
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        backtracing(digits, 0);
        return this -> result; 
    }
};