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

nand return all possible combinations of its factors.

Note:

- Each combination’s factors must be sorted ascending, for example: The factors of 2 and 6 is
`[2, 6]`

, not`[6, 2]`

.- You may assume that
nis always positive.- Factors should be greater than 1 and less than
n.

Examples:

input:`1`

output:[]input:

`37`

output:[]input:

`12`

output:[ [2, 6], [2, 2, 3], [3, 4] ]input:

`32`

output:[ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]

DFS approach.

When writing DFS algorithm, be aware of symmetric, which is, we must ‘retrieve spot’ after we backtrack from child nodes.

For example,

thisRes.push_back(i); DFS(n / i, res, thisRes); thisRes.pop_back(); // pop i

and

if(thisRes.size() > 0){ // single factor is not allowed due to problem specification. thisRes.push_back(n); res.push_back(thisRes); thisRes.pop_back(); }

class Solution { public: vector<vector<int>> getFactors(int n) { vector<vector<int> > res; vector<int> thisRes; DFS(n, res, thisRes); return res; } void DFS(int n, vector<vector<int> >& res, vector<int>& thisRes){ int i; i = thisRes.size() == 0? 2: thisRes.back();// i is greater than last element in thisRes. This is to avoid duplicate and make thisRes in ascending order. for(; i <= sqrt(n); i++){ if(n % i == 0){ //i is a factor of n thisRes.push_back(i); DFS(n / i, res, thisRes); thisRes.pop_back(); // pop i } } if(thisRes.size() > 0){ thisRes.push_back(n); res.push_back(thisRes); thisRes.pop_back(); } } };