C++, 0ms: Backtracking, Clean Code


  • 0

    C++, 0ms: Backtracking

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> answer;
    
        bt_solution(result, answer, k, n, 1); // Start from digit 1
        
        return result;
    }
    
    void bt_solution(vector<vector<int>>& r, vector<int>& a, int k, int n, int digit) {
        if(k == 0) {
            if(n == 0) r.push_back(a);
            return;
        }
        
        for(int i = digit; i < 10; ++i) {
            a.push_back(i);
            bt_solution(r, a, k-1, n-i, i+1); 
            a.pop_back();
        }
    }
    

  • 0
    F

    Good solution.

    if(k == 0){
        if(n == 0) r.push_back(a);
        return;
    }
    

    can be optimized to

    if (k == 0 || n <= 0) {
        if (k == 0 && n == 0) r.push_back(a);
        return;
    }
    

  • 0

    @fei26

    Right. I was assuming that the input n will always be larger than 0.
    Consider the input n might be <= 0, we could early out before we even run the solution function.

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        
        if(n <= 0) { // If n is less and equal to 0, there is no answer.
            vector<int> answer; 
            bt_solution(result, answer, k, n, 1); 
        }
    
        return result;
    }
    
    void bt_solution(vector<vector<int>>& r, vector<int>& a, int k, int n, int start) {
        if(k == 0) {
            if(n == 0) r.push_back(a);
            return;
        }
        
        for(int i = start; i < 10; ++i) {
            a.push_back(i);
            bt_solution(r, a, k-1, n-i, i+1);
            a.pop_back();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.