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:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Example 1:
Input: 1
Output: []
Example 2:
Input: 37
Output:[]
Example 3:
Input: 12
Output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
Example 4:
Input: 32
Output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
combination
standard DFS
// for (int i = start; i <= n; i++) {注意i可以等于N
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> ans = new ArrayList<>();
if ( n <= 1) {
return ans;
}
dfs(ans, new ArrayList<>(), n, 2);
return ans;
}
public void dfs(List<List<Integer>> ans, ArrayList<Integer> part, int n, int start) {
if (n == 1) {
if (part.size() > 1) {
ans.add(new ArrayList<Integer>(part));
return;
}
}
for (int i = start; i <= n; i++) {
if (n % i == 0) {
part.add(i);
dfs(ans, part, n / i, i);
part.remove(part.size() - 1);
}
}
}
}