题目：

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: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. 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]]

链接： 

题解：

求一个数的所有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
     
      
       > getFactors(int n) {        List
       
        
         > res = new ArrayList<>();        List
         
           list = new ArrayList<>();        getFactors(res, list, n, 2);        return res;    }        private void getFactors(List
          
           
            > res, List
            
              list, int n, int factor) { if(n <= 1) { if(list.size() > 1) res.add(new ArrayList
             
              (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
     
      
       > getFactors(int n) {        List
       
        
         > res =  new ArrayList<>();        if (n <= 1) return res;        getFactors(res, new ArrayList<>(), n, 2);        return res;    }        private void getFactors(List
         
          
           > res, List
           
             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
     
      
       > getFactors(int n) {        List
       
        
         > res =  new ArrayList<>();        if (n <= 1) return res;        getFactors(res, new ArrayList<>(), n, 2);        return res;    }        private void getFactors(List
         
          
           > res, List
           
             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: