(25/60)组合总和Ⅲ、电话号码的字母组合

组合总和Ⅲ

leetcode：216. 组合总和 III

回溯法

思路

组合的基础上，在找组合的过程中，把和为N的记录下来。

复杂度分析

时间复杂度：O(C(K,9))。

空间复杂度：空间复杂度主要来自递归调用时维护的栈空间和存储结果的二维数组，分别为O(k) 和O(C(K,9)*K)。

注意点

略

代码实现

class Solution {
public:
    // 找全部组合的过程中，把和为n的记录下来
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int k,int n,int begin){
        // 终止条件，组合有k个数
        if(path.size() == k){
            int sum = 0;
            for(int i : path) sum += i;
            if(sum == n) result.push_back(path);
            return;
        }

        for(int i = begin;i <= 9 - (k - path.size()) + 1;i++){
            path.push_back(i);
            backtracking(k,n,i + 1);
            path.pop_back();
        }    
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,1);
        return result;
    }
};

电话号码的字母组合

leetcode：17. 电话号码的字母组合

回溯法

思路

首先建立数字对应的映射数组。

1. 传入digits数字字符串、index表示当前处理数字字符串的位置、path表示数字映射的结果。
2. 终止条件：首先，若digits为空，直接返回；处理完（index>=digits的大小）digits里的数字后，把path存入结果数组，返回。
3. 递归体：
   1. 首先通过index从digits字符串中获取当前处理的数字。
   2. 对数字映射的字符集进行遍历，递归。

复杂度分析

时间复杂度：O(3^m * 4^n)，其中 m 是对应四个字母的数字个数，n 是对应三个字母的数字个数。

空间复杂度：O(3^m * 4^n)。

注意点

1. string数字转化为int数字，减去'0'。

代码实现

class Solution {
public:
    // 还是组合问题
    vector<string> result;
    string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };

    void backtracking(string digits,int index,string path){
        if(digits.size() == 0) return;
        if(index >= digits.size()){	// 终止条件：当前处理的index>=size，已经处理完元素了
            result.push_back(path);
            return;
        }
        int number = digits[index] - '0'; // 获取当前处理的数字
        for(int i = 0;i < letterMap[number].size();i++){	// 对数字映射的字符遍历
            backtracking(digits,index + 1,path + letterMap[number][i]);
        }
    }

    vector<string> letterCombinations(string digits) {
        backtracking(digits,0,"");
        return result;
    }
};