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:
Example 1:
Input:1Output: []Example 2:
Input:37Output:[]Example 3:
Input:12Output: [ [2, 6], [2, 2, 3], [3, 4] ]Example 4:
Input:32Output: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]
因子的组合。题意是给一个整数N，请你返回他所有的因子组合。
思路是回溯。我这里首先提供一个未剪枝的做法。代码还是用到大部分回溯类的题都需要用的模板，需要用到一个helper函数。函数中的N的含义是试图被整除的数字。
时间O(n!)
空间O(n)
Java实现
1 class Solution { 2 public List<List<Integer>> getFactors(int n) { 3 List<List<Integer>> res = new ArrayList<>(); 4 helper(res, new ArrayList<>(), n, 2); 5 return res; 6 } 7 8 // n - the number we are trying to divide 9 // start = the first dividor we try 10 private void helper(List<List<Integer>> res, List<Integer> list, int n, int start) { 11 if (n == 1) { 12 if (list.size() > 1) { 13 res.add(new ArrayList<>(list)); 14 return; 15 } 16 } 17 for (int i = start; i <= n; i++) { 18 if (n % i == 0) { 19 list.add(i); 20 helper(res, list, n / i, i); 21 list.remove(list.size() - 1); 22 } 23 } 24 } 25 }
其次是一个剪枝了的做法，速度提高不少。注意16行，在遍历一个数字的因数的时候，其实当你找到第一个大于1的因数i的时候，最大的因数就是这个数字除以i。举个例子，比如你找到了8的最小因数2，8的最大因数会是8 / 2 = 4。但是为什么这个剪枝了的做法的base case会跟前一种做法不一样呢？还是拿8举例子，i在递归函数里会是这样变化的
第一轮一开始16行i = 2，进入19行的时候，n / i = 8 / 2 = 4
第二轮递归的时候，i = 2，n / i = 4 / 2 = 2
这样会导致再下一轮递归的时候，如果i继续等于2的话，n / i = 2 / 2 = 1，会导致16行的for loop根本跑不起来。此时list里面只有两个2，但是为了得到8，其实你需要3个2。
Java实现
1 class Solution { 2 public List<List<Integer>> getFactors(int n) { 3 List<List<Integer>> res = new ArrayList<>(); 4 helper(res, new ArrayList<>(), n, 2); 5 return res; 6 } 7 8 // n - the number we are trying to divide 9 // start = the first dividor we try 10 private void helper(List<List<Integer>> res, List<Integer> list, int n, int start) { 11 if (!list.isEmpty()) { 12 list.add(n); 13 res.add(new ArrayList<>(list)); 14 list.remove(list.size() - 1); 15 } 16 for (int i = start; i <= n / i; i++) { 17 if (n % i == 0) { 18 list.add(i); 19 helper(res, list, n / i, i); 20 list.remove(list.size() - 1); 21 } 22 } 23 } 24 }
[LeetCode] 254. Factor Combinations
原文：https://www.cnblogs.com/cnoodle/p/13270328.html