Problem

Numbers can be regarded as product of its factors. For example,

1
2

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. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

Examples

Example 1:

1
2
3

Input: n = 1
Output:
 []

Example 2:

1
2
3

Input n = 37
Output:
[]

Example 3:

1
2
3
4
5
6
7

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

Example 4:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input n = 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Similar Problem

Find all unique combinations of factors for given number

Solution

Method 1 - Backtracking

We can iterate from i = 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 currFactors 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.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    private List<Integer> currFactors = 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 (!currFactors.isEmpty()) {
	        List<Integer> subAns = new ArrayList<>(currentFactors);
	        subAns.add(n);
            ans.add(subAns);
        }
        for (int j = i; j <= n / j; j++) {
            if (n % j == 0) {
                currFactors.add(j);
                dfs(n / j, j);
                currFactors.remove(currFactors.size() - 1); // backtrack
            }
        }
    }
}

Dry Run

Take eg. 3, n = 12.

We start DFS with n = 12, i = 2

DFS Level 0
1
2
3
4
5

n = 12, i = 2
currFactors is empty, so nothing to do
j = 2, L = n / j = 6; j <= L and n %j == 0 is true
currFactors = [2]
dfs(6, 2)

This opens up a new recursion call

DFS Level 1
1
2
3
4
5
6
7

n = 6, i = 2
currFactors = [2] is not empty, so ans += (currFactors + n) =[[2, 6]]


j = 2, , L = n / j = 3; j <= L and n % 2 == 0 is true
currFactors = [2, 2]
dfs(3, 2)

Now, we got to next recursion call:

DFS Level 2
1
2
3
4
5
6
7
8

n = 3, i = 2
currFactors = [2, 2] is not empty, so ans += (currFactors + n)
currFactors + n = [2, 2, 3]
ans =[[ 2, 6 ], [2, 2, 3]]

j = 2, , L = n / j = 1; j <= L is false, hence we won't enter the loop

We backtrack to dfs level 1

and so on.

DFS Level 1
1
2
3
4
5

n = 6, i = 2

Now, we pop out last added 2 currFactors
currFactors = [2]
j = 3, L = n / j = 2. j <= L is false, hence our loop is done. We got to dfs level 0
DFS Level 0
1
2
3
4
5
6
7

n = 12, i = 2

Now, we pop out last added 2 currFactors
currFactors = []
j = 3, L = n / j = 4; j <= L and n %j == 0 is true
currFactors = [3]
dfs(4, 3)
New DFS Level 1
1
2
3
4
5
6

n = 4, i = 3
currFactors = [3] is not empty, so ans += (currFactors + n)
currFactors + n = [3, 4]
ans =[[ 2, 6 ], [2, 2, 3], [3, 4]]

j = 3,  L = n / j = 1. j <= L is false, hence our loop is done. We got to dfs level 0
DFS Level 0
1
2
3
4
5

n = 12, i = 2

Now, we pop out last added 3 currFactors
currFactors = []
j = 4, L = n / j = 3; j <= L is false, hence we are out of loop, and our DFS is over.
Ans

Hence, eventually, [[ 2, 6 ], [2, 2, 3], [3, 4]] is answer.