LeetCode Q216 Combination Sum III

Question:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Solution: Backtracking –0ms

class Solution {
public:
    void helper( vector<vector<int>>& res, int k, int n, vector<int>& ans, int start ){
        if ( n < 0 ) 
            return;
        if ( k == ans.size() ){
            if ( 0 == n )
                res.push_back( ans );
            return;
        }
        
        for( int j = start; j <= 9; ++j ){
            ans.push_back( j );
            helper( res, k, n - j, ans, j + 1 );
            ans.pop_back();
        }
        
    }
    vector<vector<int>> combinationSum3( int k, int n ) {
        vector<vector<int>> res;
        if ( k > 0 && n > 0 ){
            vector<int> ans;
            helper( res, k, n, ans, 1 );
        }
        return res;    
    }
        
};