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: 

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

這道題給了我們一個正整數n，讓我們寫出所有的因子相乘的形式，而且規定了因子從小到大的順序排列，那麼對于這種需要列出所有的情況的題目，通常都是用回溯法來求解的，由于題目中說明了1和n本身不能算其因子，那麼我們可以從2開始周遊到n，如果目前的數i可以被n整除，說明i是n的一個因子，我們将其存入一位數組out中，然後遞歸調用n/i，此時不從2開始周遊，而是從i周遊到n/i，停止的條件是當n等于1時，如果此時out中有因子，我們将這個組合存入結果res中

public class GetFactor {
    public static List<List<Integer>> getFactor(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> out = new ArrayList<>();
        helper(n, 2, out, res);
        return res;
    }
    
    private static void helper(int n, int start, List<Integer> out,
            List<List<Integer>> res) {
        if (n == 1) {
            if (out.size() > 1) {
                res.add(new ArrayList<>(out));
            }
        } else {
            for (int i = start; i <= n; i++) {
                if (n % i == 0) {
                    out.add(i);
                    helper(n / i, i, out, res);
                    out.remove(out.size() - 1);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        System.out.println(getFactor(12));
    }
}