216. Combination Sum III

This is a combination problem so the intuition is to use backtracking algorithm. A trick here is for the for loop, the start will be the last number from the result of last iteration and the end will be 9 because duplicated number is not allowed. Let's see an example why we do this way.

Input k = 3, n = 9
R1,  R2,    R3
[1], [1, 2], [1, 2, 6]
       [1, 3], [1, 3, 5]
       [1, 4...9]
[2], [2, 3], [2, 3, 4]
       [2, 4...9]
[3...9]

From the example we can see, that we should start from the last number from the result of last iteration. If we don't, then we'll introduce duplicated solutions.

1:  class Solution {  
2:  private:  
3:    vector<vector<int>> res;  
4:  public:  
5:    vector<vector<int>> combinationSum3(int k, int n) {  
6:      vector<int> sol;  
7:      helper(k, n, sol);  
8:      return res;  
9:    }  
10:    void helper(int k, int n, vector<int> &sol) {  
11:      if (k > n || (k == 0 && n != 0)) return;  
12:      if (k == 0 && n == 0) {  
13:        res.push_back(sol);  
14:        return;  
15:      }  
16:      for (int i = sol.empty() ? 1 : sol.back()+1; i < 10; i++) {  
17:        sol.push_back(i);  
18:        helper(k-1, n-i, sol);  
19:        sol.pop_back();  
20:      }  
21:      return;  
22:    }  
23:  };