# Leetcode: Factor Combinations

By | 2018 年 9 月 22 日

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:

You may assume that n is always positive.
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]
]
```

## Analyze

Recursively get the factors of n by checking the numbers in range from 2 to n/2. If the number is a factor of n, then recursively get the factors list of the counterpart.

Use a map from integer to factors list to speedup the process.

## Solutions

### Ruby

```# @param {Integer} n
# @return {Integer[][]}
def get_factors(n)
@saved_factors ||= {}
return @saved_factors[n] unless @saved_factors[n].nil?

factors = []
2.upto(n/2) do |i|
if n % i == 0
j = n / i
factors &lt;&lt; [i, j] if i &lt;= j
factors_j = get_factors(j)
factors += factors_j.select{|fj| fj.first &gt;= i}.map{|fj| [i] + fj}
end
end

@saved_factors[n] = factors
end
```

Beats 100% ruby solutions with cache:

### Java

```class Solution {
private Map<integer, list=""    <list<integer="">&gt;&gt; cache;</integer,>

public Solution() {
this.cache = new HashMap<integer, list=""   <list<integer="">&gt;&gt;();
}</integer,>

private List<integer> pair(int i, int j) {
List<integer> list = new ArrayList<integer>(2);
return list;
}</integer></integer></integer>

private List<integer> extendFactor(int i, List<integer> sourceFactors) {
List<integer> list = new ArrayList<integer>(sourceFactors.size() + 1);
for(Integer j : sourceFactors) {
}
return list;
}</integer></integer></integer></integer>

public List

<list<integer>&gt; getFactors(int n) {
// System.out.println("get:" + n);
if(this.cache.containsKey(n)) {
return this.cache.get(n);
}</list<integer>List

<list<integer>&gt; factors = new ArrayList
<list<integer>&gt;();
for(int i = 2; i &lt;= n / 2; ++i) {
if(n % i != 0) {
continue;
}
// System.out.println(i);
int j = n / i;
if(i &lt;= j) {
}
List

<list<integer>&gt; factorsForJ = getFactors(j);
for(List<integer> factorJ : factorsForJ) {
if(factorJ.get(0) &gt;= i) {