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

216.组合总和III

1.有了昨天做77.组合的经验，这题也是一样的思路，无非是多了个判断条件组合总和是否=n。（for循环内已经做了初步剪枝）

class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int startIndex){
    if(path.size()==k){
        int sum=0;
        for(int i=0;i<k;i++){
            sum+=path[i];
        }
        if(sum==n){//判断组合总和是否=n
            result.push_back(path);
            return;
        }
        else return;
    }
    for(int i=startIndex;i<=10-(k-path.size());i++){
        path.push_back(i);//处理结点
        backtracking(n,k,i+1);//递归
        path.pop_back();//回溯
    }
}
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(n,k,1);
        return result;
    }
};

2.这题我们还有一个更进一步的剪枝思路，因为我们循环时i是逐渐增大的。所以，当某一刻我们发现组合之和已经>n时，说明后面的组合之和也一定>n不满足条件了，就不用继续递归了，直接结束递归返回。

class Solution {
private:
int sum=0;
vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int startIndex){
    if(sum>n) return;//剪枝
    if(path.size()==k){
        if(sum==n){//判断组合总和是否=n
            result.push_back(path);
            return;
        }
        else return;
    }
    for(int i=startIndex;i<=10-(k-path.size());i++){
        sum+=i;
        path.push_back(i);//处理结点
        backtracking(n,k,i+1);//递归
        path.pop_back();//回溯
        sum-=i;
    }
}
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(n,k,1);
        return result;
    }
};

17.电话号码的字母组合

1.其实本题的回溯部分倒不是很难理解，反而是电话数字与字母之间的映射关系不容易想到。

class Solution {
private:
string letterMap[10]={//二维数组映射数字与字母的关系
    "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};
string path;
vector<string> result;
void backtracking(string str,int size,int index){
    if(path.size()==size){
        result.push_back(path);//把组合结果加入返回数组
        return;
    }
    int digit=str[index]-'0';//把字符串中数字转化为整型
    string letter=letterMap[digit];//根据映射关系，找出数字对应的字符串
    for(int i=0;i<letter.size();i++){//遍历字符串枚举组合
        path.push_back(letter[i]);
        backtracking(str,size,index+1);//递归处理后面数字对应的字符串
        path.pop_back();//回溯
    }
}
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return result;//空字符串特殊处理
        backtracking(digits,digits.size(),0);
        return result;
    }
};

今日总结：她总是只留下电话号码~