http://www.lintcode.com/en/problem/factorization/

A non-negative numbers can be regarded as product of its factors. Write a function that takes an integer n and return all possible combinations of its factors.

Notice

Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combination.

Example Given n = 8 return [[2,2,2],[2,4]] // 8 = 2 x 2 x 2 = 2 x 4. Given n = 1 return [] Given n = 12 return [[2,6],[2,2,3],[3,4]]

解题：找出所以因子乘积组合。

public class Solution {
    /**
     * @param n an integer
     * @return a list of combination
     */

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> getFactors(int n) {
        // write your code here
        dfs(2, n);
        return ans;
    }

    void dfs(int start, int remain) {
        if (remain == 1) {
            if (path.size() != 1)
                ans.add(new ArrayList<Integer>(path));
            return;
        }

        for (int i = start; i <= remain; i++) {
            //once i is not divied, break out
            if (i > remain / i) {
                break;
            }
            //once find a factor
            if (remain % i == 0) {
                path.add(i);
                dfs(i , remain / i);
                path.remove(path.size() - 1);
            }
        }

        path.add(remain);
        dfs(remain, 1);
        path.remove(path.size() - 1);
    }
}