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:
output:
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] ]Solution 1: DFS
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<Integer> one=new ArrayList<>();
List<List<Integer>> res=new ArrayList<>();
for (int i=2; i*i<=n; i++) dfs(i,n,one,res);
return res;
}
private void dfs(int d, int n, List<Integer> one, List<List<Integer>> res) {
if (n%d!=0) return;
one.add(d);
n/=d;
one.add(n);
res.add(new ArrayList<Integer>(one));
one.remove(one.size()-1);
for (int i=d; i*i<=n; i++) dfs(i,n,one,res);
one.remove(one.size()-1);
}
}
没有评论:
发表评论