Question

Formatted question description: https://leetcode.ca/all/254.html

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

Algorithm

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)

Code

• import java.util.ArrayList;
import java.util.List;

public class Factor_Combinations {

public static void main(String[] args) {
Factor_Combinations out = new Factor_Combinations();
Solution s = out.new Solution();

System.out.println(s.getFactors(32));
}

public class Solution {

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> getFactors(int n) {

if (n <= 3) {
return result;
}

dfs(2, n, new ArrayList<Integer>());

return result;
}

private void dfs(int start, int target, ArrayList<Integer> onePath) {

if (target <= 1) {
if (onePath.size() > 1) { // to avoid case: n=32, and only 32 in this list
}
return;
}

// start is always 2, can be removed, and hardcode to 2
for (int i = start; i <= target; i++) { // note: <=, eg: i=2, target=2

if (target % i == 0) {
dfs(i, target / i, onePath); // not i+1, but i => example: 32, then 2,2,2...
onePath.remove(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]]:
ans = []

def dfs(n: int, s: int, path: List[int]) -> None:
if n <= 1:
if len(path) > 1:
ans.append(path.copy())
return

# always starting at 2
for i in range(s, n + 1):
if n % i == 0:
path.append(i)
dfs(n // i, i, path)
path.pop()

dfs(n, 2, [])  # The smallest factor is 2
return ans

############

class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
res = []
self.dfsHelper(n, res, [], 2)
return res[1:]

def dfsHelper(self, n, res, path, start):
if len(path) > 1 and path[-2] > path[-1]:
return

if n == 1:
res.append(path + [])
return

path.append(n)
self.dfsHelper(n / n, res, path, n)
path.pop()

for i in range(start, int(n ** 0.5) + 1):
if n % i == 0:
path.append(i)
self.dfsHelper(n / i, res, path, i)
path.pop()


• func getFactors(n int) [][]int {
t := []int{}
ans := [][]int{}
var dfs func(n, i int)
dfs = func(n, i int) {
if len(t) > 0 {
cp := make([]int, len(t))
copy(cp, t)
cp = append(cp, n)
ans = append(ans, cp)
}
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
}