LeetCode 75| 回溯

目录

17 电话号码的字母组合

216 组合总和 |||

17 电话号码的字母组合

class Solution {
private:
    vector<string>res;
    const string strs[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)return res;
        getCombinations(digits,0,"");
        return res;
    }
    void getCombinations(string digits,int cnt,string s){
        if(cnt == digits.size()){
            res.push_back(s);
            return;
        }
        int digit = digits[cnt] - '0';
        string str = strs[digit];
        for(int i = 0;i < str.size();i++){
            getCombinations(digits,cnt + 1,s + str[i]);
        }
    }

};

时间复杂度O(×)N是对应三个字母的数字个数,M是对应四个字母的数字个数

空间复杂度O(×)N是对应三个字母的数字个数,M是对应四个字母的数字个数

216 组合总和 |||

class Solution {
private:
    vector<vector<int>>res;
    vector<int>now;
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(1,0,k,n);
        return res;
    }
    void dfs(int cnt,int sum,int k,int n){
        if(sum > n)return;
        if(now.size() == k){
            if(sum == n)res.push_back(now);
            return;
        }
        for(int i = cnt;i <= 9;i++){
            now.push_back(i);
            sum += i;
            dfs(i + 1,sum,k,n);
            sum -= i;
            now.pop_back();
        }

    }
};

时间复杂度O(N ×?)N为集合的大小，本题中为9，一个有个状态(选择或者不选这个数字)

空间复杂度O(N)