https://leetcode.com/problems/factor-combinations
Description
Numbers can be regarded as the product of their factors.
For example, 8 = 2 x 2 x 2 = 2 x 4
.
Given an integer n
, return all possible combinations of its factors. You may return the answer in any order.
Note that the factors should be in the range [2, n - 1]
.
Example 1:
**Input:** n = 1
**Output:** []
Example 2:
**Input:** n = 12
**Output:** [[2,6],[3,4],[2,2,3]]
Example 3:
**Input:** n = 37
**Output:** []
Example 4:
**Input:** n = 32
**Output:** [[2,16],[4,8],[2,2,8],[2,4,4],[2,2,2,4],[2,2,2,2,2]]
Constraints:
ac
// KEY: circumvent repeat, number always <= next one
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> note = new ArrayList<Integer>();
backtrack(res, note, n, 2);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> note, int n, int s) {
// exit
if (n <= 1) {
if (note.size() > 1) {
res.add(new ArrayList<Integer>(note));
}
return;
}
// handle
for (int i = s; i <= n; i++) {
if (n % i == 0) {
note.add(i);
backtrack(res, note, n / i, i);
note.remove(note.size()-1);
}
}
}
}
ac2:
key: i = start; i <= n/i
ensure acending list
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
helper(n, 2, new ArrayList<Integer>(), res);
return res;
}
private void helper(int n, int start, List<Integer> note, List<List<Integer>> res) {
// exit
if (note.size() > 0) {
List<Integer> tmp = new ArrayList<Integer>(note);
tmp.add(n);
res.add(tmp);
}
for (int i = start; i <= n/i; i++) { // i <= n/i, list should be ascending
if (n % i != 0) continue;
note.add(i);
helper(n / i, i, note, res);
note.remove(note.size()-1);
}
}
}