Lintcode 652. 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.

Example

Example1

Input: 8
Output: [[2,2,2],[2,4]]
Explanation:
8 = 2 x 2 x 2 = 2 x 4

Example2

Input: 1
Output: []

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.

Solution 1: DFS

public class Solution {
    /**
     * @param n: An integer
     * @return: a list of combination
     */
    public List<List<Integer>> getFactors(int n) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        
        getFactorsHelper(2, n, new ArrayList<Integer>(), ans);
        
        return ans;
    }
    
    private void getFactorsHelper(int start, int n, List<Integer> curList, List<List<Integer>> ans) {
        if (n <= 1) {
            if (curList.size() > 1) {
                List<Integer> copy = new ArrayList<>(curList);
                ans.add(copy);
            }
            return;
        }
        
        for (int i = start; i <= Math.sqrt(n); i++) {
            if (n % i != 0) {
                continue;
            }
            
            curList.add(i);
            getFactorsHelper(i, n / i, curList, ans);
            curList.remove(curList.size() - 1);
        }

        curList.add(n);
        getFactorsHelper(n, 1, curList, ans);
        curList.remove(curList.size() - 1);
    }
}

Solution 2: DFS + Memo

public class Solution {
    /**
     * @param n: An integer
     * @return: a list of combination
     */
    public List<List<Integer>> getFactors(int n) {
        // write your code here
        Map<Integer, List<List<Integer>>> memo = new HashMap<>();
        
        List<List<Integer>> ans = getFactorsHelper(2, n, memo);
        ans.remove(ans.size() - 1);
        
        return ans;
    }
    
    private List<List<Integer>> getFactorsHelper(int start, int n, Map<Integer, List<List<Integer>>> memo) {
        List<List<Integer>> ans = new ArrayList<>();
        if (n <= 1) {
            return ans;
        }
        
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i != 0) {
                continue;
            }
            
            List<List<Integer>> curList = getFactorsHelper(i, n / i, memo);
            
            for (List<Integer> list : curList) {
                if (i > list.get(0)) {
                    continue;
                }
                List<Integer> copy = new ArrayList<>(list);
                copy.add(0, i);
                ans.add(copy);
            }
        }
        
        List<Integer> last = new ArrayList<>();
        last.add(n);
        ans.add(last);
        
        memo.put(n, ans);
        return ans;
    }
}