Factor Combinations

犯错，backtracking里面 for循环一定要循环到remain，因为remain自身也是自身的factor

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. You may assume that n is always positive.

2. Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

时间复杂度

https://stackoverflow.com/questions/45662736/how-to-find-the-time-complexity-of-dfsbacktracking-algorithms

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> list = new ArrayList<>();
        
        if(n <= 1)
            return list;
        
        backtracking(list,new ArrayList<>(), n,2);
        
        return list;
    }
    
    public void backtracking(List<List<Integer>> list, List<Integer> tmpList, int remain, int factor){
        
        
        if(remain <=1){
            
            //判断是 是1 和自身 还是别的factor 组合
            if(tmpList.size() > 1){
                list.add(new ArrayList<>(tmpList));
                
            }
            
            return;
        }
        
        //注意i要走到等于remain
        for(int i = factor ; i <= remain; i++ ){
            //保证能整除
            if(remain % i ==0){
                tmpList.add(i);
            //factor 是可以重复用的，所以还传factor，不用factor +1
            backtracking(list,tmpList,remain/i, i);
            
            tmpList.remove(tmpList.size()-1);
            }
            
        }
        
        
        
            
    }
}