LeetCode 254 - Factor Combinations

作者 QIFAN 日期 2017-02-03
LeetCode 254 - Factor Combinations

原题链接: 254. Factor Combinations


题干

给定一个数字 n ,返回所有的因子组合。

因子要大于 1 小于 n 。假设 n > 0 。

思路

我的第一想法是动态规划。状态方程为 $f(n) = \sum f(n \div factor)$ 。解释就是 n 的因子组合 = n 整除某个因子后的数字的因子组合的总和。为了避免重复,因子都是升序加入。

代码:

public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> curr = new ArrayList<>();
for (int i = 2; i < n; i++) {
if (n % i == 0) {
curr.add(i);
getFactors(n / i, curr, res);
curr.remove(0);
}
}
return res;
}
private void getFactors(int n, List<Integer> curr, List<List<Integer>> res) {
int lastSize = curr.size();
for (int i = curr.get(lastSize - 1); i <= n; i++) {
if (n % i == 0) { // 如果能整除
curr.add(i);
getFactors(n / i, curr, res);
curr.remove(lastSize);
}
}
// base case
if (n >= curr.get(lastSize - 1)) { // 升序的因子避免重复
List<Integer> element = new ArrayList(curr);
element.add(n);
res.add(element);
}
}