LintCode 1308

因子组合

题目描述
数字可以被视为其因数的乘积。例如，
8 = 2 x 2 x 2; = 2 x 4。20
编写一个函数，可以输入整数n并返回其因子的所有可能组合。
您可以假设n总是正数。
因数应大于1且小于n。

扫码免费做题
↓↓↓

样例 1
输入: 12输出: [ [2, 6], [2, 2, 3], [3, 4]]解释:2*6 = 122*2*3 = 123*4 = 12
样例 2
输入: 32输出: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8]]解释:2*16=322*2*8=322*2*2*4=322*2*2*2*2=322*4*4=324*8=32
解题思路
dfs搜索所有的因子组合
源代码
publicclassSolution{/** * @param n: a integer * @return: return a 2D array */publicList<List<Integer>> getFactors(int n) {// write your code hereList<List<Integer>> result = new ArrayList<List<Integer>>(); helper(result, new ArrayList<Integer>(), n, 2);return result; }public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){if (n <= 1) {if (item.size() > 1) { result.add(new ArrayList<Integer>(item)); }return; }for (int i = start; i <= n; ++i) {if (n % i == 0) { item.add(i); helper(result, item, n/i, i); item.remove(item.size()-1); } } }}
查看完整代码，向左滑动
点击【阅读原文】，查看领扣原题。
继续阅读
阅读原文