77. Combinations

A typical backtracking solution.

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

When I revisited this problem, I had a more concise solution as following.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> combine(int n, int k) {  
4:      vector<int> sol;  
5:      vector<vector<int>> res;  
6:      helper(n, 1, k, sol, res);  
7:      return res;  
8:    }  
9:    void helper(int n, int start, int k, vector<int> sol, vector<vector<int>> &res) {  
10:      if (k == 0) { res.push_back(sol); return; }  
11:      for (int i = start; i <= n; i++) {  
12:        sol.push_back(i);  
13:        helper(n, i+1, k-1, sol, res);  
14:        sol.pop_back();  
15:      }  
16:    }  
17:  };