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:

You may assume that n is always positive.

Factors should be greater than 1 and less than n.

递归

复杂度

O(2^N) 时间 O(N) 空间

思路

递归，为了防止2,2,3和2,3,2这种重复，参数里需要一个start

递归函数接口定义：

helper函数找n的所有因式分解，每个因式分解最小的因子从start开始，后面的因子们升序排列，把所有这样的因式分解放到result里

void helper(int n,    //对谁进行因式分解            int start,     //最小的因子有多大            List
    
      list,    //分解到n之前的因子们            List
     
      
       > result)    //结果
      
     
    

注意

输入的数不算做自己的因子

最开始的循环for(int i = start; i <= n; i++)非常费时，做了很多没用的事，可以这样：for (int i = start; i <= sqrt(n); i++)这样省去了大量的无用计算，时间从228ms降到2ms，有100倍之多。但是这样写会漏掉一种情况,就是n为因子的情况，加进去即可。

代码

public class Solution {    public List
    
     
      > getFactors(int n) {        List
      
       
        > result = new ArrayList<>();        List
        
          list = new ArrayList<>();        helper(n, 2, list, result);        return result;    }    public void helper(int n, int start, List
         
           list, List
          
           
            > result) { if (n == 1) { if (list.size() > 1) { //the original input is not counted in result.add(new ArrayList
            
             (list)); } return; } for (int i = start; i <= Math.sqrt(n); i++) { //这里只要到根号n就好了 if (n % i == 0) { list.add(i); helper(n / i, i, list, result); list.remove(list.size() - 1); } } list.add(n); //把n加进去 helper(1, n, list, result); list.remove(list.size() - 1); }}