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.

**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]
]

一刷
題解： DFS + backtracking， 265 ms

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(res, list, n, 2);
        return res;
    }
    
    public void dfs(List<List<Integer>> res, List<Integer> list, int n, int start){
        if(n<=1){
            if(list.size()>1) res.add(new ArrayList<>(list));
            return;
        }
        
//由于end可能包含自己称勋，如4=2*2，第二次recursion傳入2，于是有等號(hào)，list加入res時(shí)要判斷size是否大于1
        for(int i=start; i<=n; i++){
            if(n%i == 0){
                list.add(i);
                dfs(res, list, n/i, i);
                list.remove(list.size()-1);
            }
        }
    }
}

方法2衣吠， factor都是成雙成對(duì)出現(xiàn)的倍谜，例如如果n%i == 0, 那么 {i, n/i}一定是滿足條件的一個(gè)解。2ms

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        if(n <= 3)  return ret;
        List<Integer> path = new LinkedList<Integer>();
        getFactors(2, n, path, ret);
        return ret;
    }
    
    private void getFactors(int start, int n, List<Integer> path, List<List<Integer>> ret){
       for(int i = start; i <= Math.sqrt(n); i++){
           if(n % i == 0 && n/i >= i){  // The previous factor is no bigger than the next
               path.add(i);
               path.add(n/i);
               ret.add(new LinkedList<Integer>(path));
               path.remove(path.size() - 1);
//下次的start = I, 保證不會(huì)再拆出比左邊更小的弄息，避免重復(fù)
               getFactors(i, n/i, path, ret);
               path.remove(path.size() - 1);
           }
       }
    }
}

二刷
同上

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