leetcode刷题

组合总和

在返回的结构上加上一个判断就可以。

void backing(vector<vector<int>> &result, vector<int> &path, int k, int n, int starti){
        if(path.size() == k){
            int sum = 0;
            for(auto i : path){
                sum += i;
            }
            if(sum == n){
                result.push_back(path);
            }  
            return;
        }

        for(int i = starti; i <= 9; i++){		//这种写法要比上面那个清楚简洁一些。
            path.push_back(i);
            backing(result, path, k, n, i+1);
            path.pop_back();

        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> path;
        backing(result, path, k, n, 1);
        return result;
    }

电话号码

一样的套路，只是写的太繁琐了。

void backing(string digits, vector<string> &result, string &path){
        if( digits.size() != 0  && path.size() == digits.size()){
            result.push_back(path);
            return;
        }

        if(digits[path.size()] == '2'){
            //cout<<'=====';
            for(int i = 1; i <= 3; i++){
                path.push_back(char('a' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '3'){
            for(int i = 1; i <= 3; i++){
                path.push_back(char('d' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '4'){
            for(int i = 1; i <= 3; i++){
                path.push_back(char('g' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '5'){
            for(int i = 1; i <= 3; i++){
                path.push_back(char('j' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '6'){
            for(int i = 1; i <= 3; i++){
                path.push_back(char('m' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '7'){
            for(int i = 1; i <= 4; i++){
                path.push_back(char('p' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '8'){
            for(int i = 1; i <= 3; i++){
                path.push_back(char('t' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
        if(digits[path.size()] == '9'){
            for(int i = 1; i <= 4; i++){
                path.push_back(char('w' + i - 1));
                backing(digits, result, path);
                path.pop_back();
            }
        }
       
        return;
    }
     vector<string> letterCombinations(string digits) {
        vector<string> result;
        string path;
        backing(digits, result, path);
        return result;     
    }