254. Factor Combinations

题目：

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: 

Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].

You may assume that n is always positive.

Factors should be greater than 1 and less than n.

 

Examples: 
input: 1
output: 

[] input: 37
output: 
[] input: 12
output:
[[2, 6],[2, 2, 3],[3, 4] ] input: 32
output:
[[2, 16],[2, 2, 8],[2, 2, 2, 4],[2, 2, 2, 2, 2],[2, 4, 4],[4, 8] ]

链接： http://leetcode.com/problems/factor-combinations/

题解：

求一个数的所有factor，这里我们又想到了DFS + Backtracking， 需要注意的是，factor都是>= 2的，并且在此题里，这个数本身不能算作factor，所以我们有了当n <= 1时的判断 if(list.size() > 1) add the result to res.

Time Complexity - O(2ⁿ)， Space Complexity - O(n).

public class Solution {public List<List<Integer>> getFactors(int n) {List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();getFactors(res, list, n, 2);return res;}private void getFactors(List<List<Integer>> res, List<Integer> list, int n, int factor) {if(n <= 1) {if(list.size() > 1)res.add(new ArrayList<Integer>(list));return;}for(int i = factor; i <= n; i++) {if(n % i == 0) {list.add(i);getFactors(res, list, n / i, i);list.remove(list.size() - 1);}}} }

 

二刷：

还是使用了一刷的办法，dfs + backtracking。但递归结束的条件更新成了n == 1。 但是速度并不是很快，原因是没有做剪枝。我们其实可以设置一个upper limit，即当i > Math.sqrt(n)的时候，我们不能继续进行下一轮递归，此时就要跳出了。

Java:

public class Solution {public List<List<Integer>> getFactors(int n) {List<List<Integer>> res = new ArrayList<>();if (n <= 1) return res;getFactors(res, new ArrayList<>(), n, 2);return res;}private void getFactors(List<List<Integer>> res, List<Integer> list, int n, int pos) {if (n == 1) {if (list.size() > 1) res.add(new ArrayList<>(list));return;}for (int i = pos; i <= n; i++) {if (n % i == 0) {list.add(i);getFactors(res, list, n / i, i);list.remove(list.size() - 1);}}} }

 

Update: 使用@yuhangjiang的方法，只用计算 2到sqrt(n)的这么多因子，大大提高了速度。

public class Solution {public List<List<Integer>> getFactors(int n) {List<List<Integer>> res = new ArrayList<>();if (n <= 1) return res;getFactors(res, new ArrayList<>(), n, 2);return res;}private void getFactors(List<List<Integer>> res, List<Integer> list, int n, int pos) {for (int i = pos; i <= Math.sqrt(n); i++) {if (n % i == 0 && n / i >= i) {list.add(i);list.add(n / i);res.add(new ArrayList<>(list));list.remove(list.size() - 1);getFactors(res, list, n / i, i);list.remove(list.size() - 1);}}} }

 

 

 

 

Reference:

https://leetcode.com/discuss/51261/iterative-and-recursive-python

https://leetcode.com/discuss/87926/java-2ms-easy-to-understand-short-and-sweet

https://leetcode.com/discuss/58828/a-simple-java-solution

https://leetcode.com/discuss/72224/my-short-java-solution-which-is-easy-to-understand 

https://leetcode.com/discuss/82087/share-bit-the-thought-process-short-java-bottom-and-top-down

总结

以上是生活随笔为你收集整理的254. Factor Combinations的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。