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