254. Factor Combinations

Medium (LinkedIn, Uber)

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:

You may assume that n is always positive. 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] ]

public class Solution {

// test case:
// n is less than or equal to 1
// n is equal to 1

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    if(n <= 1) {
        return ans;
    } 

    backtrack(ans, new ArrayList<Integer>(), n, n, 2);
    return ans;
}

public void backtrack(List<List<Integer>> ans, List<Integer> list, int numLeft, int n, int start) {
    if(numLeft == 1) {
        ans.add(new ArrayList<Integer>(list));
        return;
    }

    for(int i = start; i * i <= numLeft && i <= n / 2; i++) {
        if(numLeft % i == 0) {
            list.add(i);
            backtrack(ans, list, numLeft / i, n, i);
            list.remove(list.size() - 1);
        }
    }
}

}

Improve

public class Solution {

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> current = new ArrayList<>();
    getFactorsHelper(result, n, current);
    return result;
}

public void getFactorsHelper(List<List<Integer>> result, int n, List<Integer> previous) {
    if (n <= 1) {
        return; 
    }
    ArrayList<Integer> current = new ArrayList<>(previous);
    int preNum = (current.isEmpty() ? 2 : current.get(current.size() - 1));
    for (int i = preNum; i*i <= n; i++) {
        if (n % i == 0) {
            current.add(i);
            getFactorsHelper(result, n/i, current);
            current.remove(current.size() - 1);
        }
    }
    if (current.size() != 0) {
        current.add(n);
        result.add(current);
    }
}

}