# 254. Factor Combinations

## Description

Numbers can be regarded as the product of their factors.

• For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Example 1:

Input: n = 1
Output: []


Example 2:

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


Example 3:

Input: n = 37
Output: []


Constraints:

• 1 <= n <= 107

## Solutions

Iterate from 2 to n. If the current number i is divisible by n, it means that i is a factor of n. Store it in a onePath list, and then recursively call n/i.

At next recursion, do not traverse from 2. It traverses from i to n/i, and the condition for stopping is when n is equal to 1, if there is a factor in onePath at this time, store this combination in the result.

### Pitfall

Need to avoid case: n=32, and only 32 in this list, add check if (onePath.size() > 1)

• class Solution {
private List<Integer> t = new ArrayList<>();
private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> getFactors(int n) {
dfs(n, 2);
return ans;
}

private void dfs(int n, int i) {
if (!t.isEmpty()) {
List<Integer> cp = new ArrayList<>(t);
}
for (int j = i; j <= n / j; ++j) {
if (n % j == 0) {
dfs(n / j, j);
t.remove(t.size() - 1);
}
}
}
}

• class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<int> t;
vector<vector<int>> ans;
function<void(int, int)> dfs = [&](int n, int i) {
if (t.size()) {
vector<int> cp = t;
cp.emplace_back(n);
ans.emplace_back(cp);
}
for (int j = i; j <= n / j; ++j) {
if (n % j == 0) {
t.emplace_back(j);
dfs(n / j, j);
t.pop_back();
}
}
};
dfs(n, 2);
return ans;
}
};

• class Solution:
def getFactors(self, n: int) -> List[List[int]]:
@cache
def dfs(n, i):
if t:
ans.append(t + [n])
# no return, continue to rest code
j = i
while j * j <= n:
if n % j == 0:
t.append(j)
dfs(n // j, j)
t.pop()
j += 1

t = []
ans = []
dfs(n, 2)
return ans


• func getFactors(n int) [][]int {
t := []int{}
ans := [][]int{}
var dfs func(n, i int)
dfs = func(n, i int) {
if len(t) > 0 {
ans = append(ans, append(slices.Clone(t), n))
}
for j := i; j <= n/j; j++ {
if n%j == 0 {
t = append(t, j)
dfs(n/j, j)
t = t[:len(t)-1]
}
}
}
dfs(n, 2)
return ans
}