LeetCode Q254: 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. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. 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]
]

Solution:
The trick here is to iterate factor from i to n/i, and insert result immediately.

	class Solution {
	public:
	void helper(vector<vector<int> >& res, int n, vector<int> subres){
	int s = subres.empty()? 2:subres.back();
	for(int i=s; i<=n/i; i++){
	vector<int> newres = subres;
	if(n%i==0){
	newres.push_back(i);
	newres.push_back(n/i);
	res.push_back(newres);
	newres.pop_back();
	helper(res, n/i, newres);
	}
	}
	}
	vector<vector<int>> getFactors(int n) {
	vector<vector<int> > res;
	vector<int> subres;
	helper(res, n, subres);
	return res;
	}
	};

view raw Q254.cpp hosted with ❤ by GitHub