254. Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

1. You may assume that n is always positive.

2. Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

vector<vector<int>> getFactors(int n) { // time: O(nlogn); space: O(logn)
    vector<vector<int> > res;
    vector<int> cur;
    helper(res, cur, n, 2);
    return res;
}
void helper(vector<vector<int> >& res, vector<int>& cur, int n, int start) {
    if (n == 1) {
        if (cur.size() > 1) res.push_back(cur);
    } else {
        for (int i = start; i <= n; ++i) {
            if (n % i != 0) continue;
            cur.push_back(i);
            helper(res, cur, n / i, i);
            cur.pop_back();
        }
    }
}

vector<vector<int>> getFactors(int n) { // time: O(sqrt(n) * log(sqrt(n))); space: O(log(sqrt(n)))
    vector<vector<int> > res;
    vector<int> cur;
    helper(res, cur, n, 2);
    return res;
}
void helper(vector<vector<int> >& res, vector<int>& cur, int n, int start) {
    if (n == 1) {
        if (cur.size() > 1) res.push_back(cur);
    } else {
        for (int i = start; i * i <= n; ++i) {
            if (n % i != 0) continue;
            cur.push_back(i);
            cur.push_back(n / i);
            res.push_back(cur);
            cur.pop_back();
            helper(res, cur, n / i, i);
            cur.pop_back();
        }
    }
}