day 25回溯（二）

day25
代码随想录
2023.12.23

1. 216组合总和Ⅲ
这这道题跟昨天组合一样，只不过加了个条件罢了，思路还是一样的

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> combinationSum3(int k, int n) {
        backtravel(k,n,1);
        return result;
    }
    void backtravel(int k, int n, int index){
        if(temp.size()==k){
            int sum=0;
            for(int i=0;i<temp.size();i++){
                sum += temp[i];
            }
            if(sum==n)
                result.push_back(temp);  
            return;
        }
            
        
        
        for(int i=index;i<=9;i++){
            temp.push_back(i);
            backtravel(k,n,i+1);
            temp.pop_back();
                
        }
            
        
    }
};

2. 17电话号码的字母组合
这道题开始看不懂，感觉很迷。首先要数字映射到字母，然后遍历字母，不断地递归。

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