代码随想录刷题随记22-回溯2

216.组合总和III

leetcode链接
注意与之前的题目不同的是需要求和。从左到右的范围尝试模型。

class Solution {
public:

    void backtrace(vector<vector<int>> &ret,int k,int n,int index,vector<int>& path,int & sum){
        if(path.size()==k){
            if(sum==n)
              ret.push_back(path);
            return ;
        }
        if(index>9)
           return;
        //选index的数字
        path.push_back(index);
        sum+=index;
        backtrace(ret,  k, n, index+1,  path,sum);
        path.pop_back();
        sum-=index;
        //不选index的数字
        backtrace(ret,  k, n, index+1,  path,sum);
        return;
    }
    
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ret;
        vector<int> path;
        int sum=0;
        backtrace(ret,  k,  n,  1,  path,sum);
        return ret;
    }
};

17.电话号码的字母组合

leetcode链接

class Solution {
public:
    const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
    };
    void backtrace(vector<string> & ret,int index,string digits,string s){
         if(index==digits.size()){
            ret.push_back(s);
            return ;
         }
         int indexdig=digits[index]-'0';
         string stringset=letterMap[indexdig];
         for(int i=0;i<stringset.size();i++){
            s.push_back(stringset[i]);
            backtrace(ret,  index+1,  digits, s);
            s.pop_back();
         }

    }
    vector<string> letterCombinations(string digits) {
       vector<string> ret;
       string s="";
       if(digits=="")
       return {};
       backtrace(ret, 0,  digits, s);
       return ret;
    }
};