Factor Combinations

Question (LC.254)

Find all possible factor combinations of a number.

Example

I: 8
O: [ [2,2,2], [2,4] ]
I: 1
O: []
I: 2
O: []
I: 9
O: [ [3,3] ]

Assume n > 0. How large can n get? n cannot be very large. what about 1? 1x1x1... Assume factors greater than 1.

Attempt #1

1. Define subproblem
    factorSearch(result, factors, dividend) => 
    add all factor combinations of dividend to result (with given prefix factors)
2. Recursive calls
    for factor from 2 to dividend / 2
        if (divident % factor != 0) continue
        factorSearch(result, factors.add(factor), divident / factor)
3. Bases cases
    if (dividend == 1)
        result.add(new List(factors))

What's wrong with this approach?

I: 12
O: [[2,2,3],[2,3,2],[2,6],[3,2,2],[3,4],[4,3],[6,2]]
E: [[2,6],[3,4],[2,2,3]]

We need to choose representative for each combination. Sorted is the easiest to work with. We want to put in the smallest factor as much as possible before we move on to a larger factor.

Corrected Code

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> result = new ArrayList<>();
    if (n < 3) {
        return result;
    }
    List<Integer> factors = new ArrayList<>();
    factorSearch(result, factors, n, 2);
    return result;
}

private void factorSearch(List<List<Integer>> result, 
                          List<Integer> factors, 
                          int dividend, 
                          int startFactor) {
    // base case
    if (dividend == 1 && factors.size() > 1) {
        result.add(new ArrayList<>(factors));
        return;
    }
    // search
    for (int factor = startFactor; factor < dividend + 1; factor++) {
        if (dividend % factor != 0) {
            continue;
        }
        factors.add(factor);
        factorSearch(result, factors, dividend / factor, factor);
        factors.remove(factors.size() - 1);
    }
}

Time & Space Complexity

Time O(n*2^n) Space O(n)