day25 组合总和Ⅲ 电话号码的字母组合

题目1：216 组合总和Ⅲ

题目链接：216 组合总和Ⅲ

题意

找出相加之和为n的k个数的组合? ?数字只可使用1~9之间的数（包括 1 9）且每个数字只能使用1遍

题目中有两个限制条件：1）k个数? ? ? 2）k个数的和为n? ? 所以最终满足条件一个的组合一定要先判断是k个数，然后再计算这k个数的和为n，只有这样才是

回溯

回溯三部曲：

1）参数和返回值

2）终止条件? ? ?叶子节点? 和为n的?k个数放入数组中

3）单层递归逻辑

sum不是参数

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int k,int n,int startIndex){
        //终止条件
        int sum = 0;
        if(path.size()==k){
            for(int i=0;i<k;i++){
                sum += path[i];
            }
            if(sum==n){
                result.push_back(path);
            }
            return;
        }
        //单层搜索逻辑
        for(int i=startIndex;i<=9;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;
    }
};

Sum作为参数

伪代码

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int targetSum,int k,int Sum,int startIndex){
        //终止条件
        if(path.size()==k){
            if(Sum==targetSum)
                result.push_back(path);
            return;
        }
        //单层搜索逻辑
        for(int i=startIndex;i<=9;i++){
            Sum += i;
            path.push_back(i);
            backtracking(targetSum,k,Sum,i+1);
            Sum -= i;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(n,k,0,1);
        return result;
    }
};

剪枝

剪枝1

剪枝2

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int targetSum,int k,int Sum,int startIndex){
        if(Sum>targetSum) return;//剪枝1 
        //终止条件
        if(path.size()==k){
            if(Sum==targetSum)
                result.push_back(path);
            return;
        }
        //单层搜索逻辑
        for(int i=startIndex;i<=9-(k-path.size())+1;i++){
            Sum += i;
            path.push_back(i);
            backtracking(targetSum,k,Sum,i+1);
            Sum -= i;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(n,k,0,1);
        return result;
    }
};

• 时间复杂度: O(n * 2^n)
• 空间复杂度: O(n)

题目2：17 电话号码的字母组合

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

题意

字符串中仅包含2-9，每个数字代表的字母和电话按键相同，返回其能表示的所有的字母组合

操作两个集合

回溯

回溯三部曲：

1）参数和返回值

2）终止条件? ?叶子节点收获结果

3）单层递归逻辑

代码

class Solution {
public:
    //数字与字符串映射  将数字下标对应到字母字符串  2->abc
    string letterMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    string path ;//存放单个结果
    vector<string> result;//存放结果集
    void backtracking(string& digits,int index){//这里注意& 
        //终止条件  index遍历到最后一个数字之后 存放结果
        if(index==digits.size()){
            result.push_back(path);
            return;
        }
        //单层递归逻辑
        //取出digits数字字符串中的单个字符 并将该字符转换为数字
        int digit = digits[index] - '0';
        //将该数字映射为字符串
        string letter = letterMap[digit];
        for(int i=0;i<letter.size();i++){
            path.push_back(letter[i]);
            backtracking(digits,index+1);//递归  将下标往后移动一个，指向下一个数字
            path.pop_back();//回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        path.clear();
        result.clear();//这里的result一定要clear 不然后面的测试用例""会报错
        if(digits.size()==0) return result;
        backtracking(digits,0);//从数字字符串中的第1个字符开始遍历
        return result;
    }
};

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