254. Factor Combinations

Backtracking solution. A trick I played here is the scanning starts from last number of candidate solution to guarantee that the solution is in an ascending order and thus duplicate is avoided.

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

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:  };