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