Combination Sum III

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]]

Runtime: 0ms

 1 class Solution {
 2 public:
 3     vector<vector<int> > combinationSum3(int k, int n) {
 4         vector<vector<int> > result;
 5         vector<int> temp;
 6         vector<int> num;
 7         
 8         for(int i = 1; i <= 9; i++)
 9             num.push_back(i);
10         
11         dfs(result, temp, num, 0, n, k);
12         return result;
13    } 
14    
15    void dfs(vector<vector<int> >& result, vector<int>& temp, vector<int> num, int start, int diff, int k){
16        if(diff == 0){
17            if(temp.size() == k)
18                result.push_back(temp);
19            return;
20        }
21        
22        for(int i = start; i < num.size(); i++){
23            if(diff < num[i]) return;
24            
25            temp.push_back(num[i]);
26            dfs(result, temp, num, i + 1, diff - num[i], k);
27            temp.pop_back();
28        }
29    }
30 };

 1 class Solution {
 2 public:
 3     vector<vector<int> > combinationSum3(int k, int n) {
 4         vector<vector<int> > result;
 5         vector<int> temp;
 6         vector<int> num;
 7         
 8         dfs(result, temp, 1, n, k);
 9         return result;
10    } 
11    
12    void dfs(vector<vector<int> >& result, vector<int>& temp, int start, int diff, int k){
13        if(diff == 0){
14            if(temp.size() == k)
15                result.push_back(temp);
16            return;
17        }
18        
19        for(int i = start; i <= 9; i++){
20            if(diff < i) return;
21            
22            temp.push_back(i);
23            dfs(result, temp, i + 1, diff - i, k);
24            temp.pop_back();
25        }
26    }
27 };