原题链接在这里：https://leetcode.com/problems/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:
- Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is
[2, 6], not[6, 2]. - You may assume that n is always positive.
- 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]
]
题解：
DFS needs state current remaining number n, current starting factor, current item list and result.
For i from starting factor to n, check if n%i == 0. If yes, we could add i to current item list and dfs to next level.
starting factor could help maintain there is no duplicate.
e.g. n = 6. When it is divided by 3, the next factor needs to start from 3. Thus there is no [3,2] added since [2, 3] is already in the list. Could use such factor to maintain distinct.
Base case 是target变成了1, 并且item的size要大于1. 这里对item 的size 有要求是因为若初始target = 12, 返回结果是不应该包含{12}这个item的.
Time Complexity: Exponential.
Space: log(target).
AC Java:
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(n<=1){
return res;
}
findFactors(n, 2, new ArrayList<Integer>(), res);
return res;
}
//注意要写好的signature
private void findFactors(int n, int factor, List<Integer> item, List<List<Integer>> res){
//base case 不但要n==1, 还需要item.size() > 1, 否则n = 2, 就会添加一个item {2}.
if(n == 1 && item.size() > 1){
res.add(new ArrayList<Integer>(item));
return;
}
for(int i = factor; i<=n; i++){
if(n%i == 0){
item.add(i);
findFactors(n/i, i, item, res);
item.remove(item.size()-1);
}
}
}
}