My Java Solution which is only 3 ms (Pre-compute a factor list)


  • 0
    L

    My idea is that the results are coming from the combination of the factors of the number, thus we can pre-compute the factors and save them in a list, therefore later we just need to pick element from this factor list.

    public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> factors = new ArrayList<Integer>();
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                if (i * i == n) {
                    factors.add(i);
                }
                else {
                    factors.add(i);
                    factors.add(n / i);
                }
            }
        }
        if (factors.size() == 0) {
            return result;
        }
        Collections.sort(factors);
        List<Integer> temp = new ArrayList<Integer>();
        getFactorsHelper(result, temp, factors, n, 0);
        return result;
    }
    public void getFactorsHelper(List<List<Integer>> result, List<Integer> temp, List<Integer> factors, int target, int start) {
        if (target == 1) {
            List<Integer> out = new ArrayList<Integer>(temp);
            result.add(out);
            return;
        }
        for (int i = start; i < factors.size(); i++) {
            int num = factors.get(i);
            temp.add(num);
            if (target % num == 0) {
                getFactorsHelper(result, temp, factors, target / num, i);
            }
            temp.remove(temp.size() - 1);
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.