254. Factor Combinations

// LeetCode URL: https://leetcode.com/problems/factor-combinations/

import java.util.ArrayList;
import java.util.List;

/**
 * Backtrackking (with optimization)
 *
 * Time Complexity: Refer: https://stackoverflow.com/a/45664178
 *
 * O(N * log(sqrt(N)) + sqrt(N))
 *
 * Space Complexity: O(sqrt(N))
 */
class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (n <= 3) {
            return result;
        }

        getFactorsHelper(result, new ArrayList<Integer>(), n, 2);
        return result;
    }

    private void getFactorsHelper(List<List<Integer>> list, List<Integer> tempList, int n, int start) {
        if (n == 1) {
            if (tempList.size() > 1) {
                list.add(new ArrayList<Integer>(tempList));
            }
            return;
        }

        for (int i = start; i * i <= n; i++) {
            if (n % i != 0) {
                continue;
            }
            tempList.add(i);
            getFactorsHelper(list, tempList, n / i, i);
            tempList.remove(tempList.size() - 1);
        }

        tempList.add(n);
        getFactorsHelper(list, tempList, 1, n);
        tempList.remove(tempList.size() - 1);
    }
}

/**
 * Backtrackking (without optimization)
 *
 * Time Complexity: Refer: https://stackoverflow.com/a/45664178
 *
 * O(N * log(N) + N)
 *
 * Space Complexity: O(N)
 */
class Solution2 {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (n <= 3) {
            return result;
        }

        getFactorsHelper(result, new ArrayList<Integer>(), n, 2);
        return result;
    }

    private void getFactorsHelper(List<List<Integer>> list, List<Integer> tempList, int n, int start) {
        if (n == 1) {
            if (tempList.size() > 1) {
                list.add(new ArrayList<Integer>(tempList));
            }
            return;
        }

        for (int i = start; i <= n; i++) {
            if (n % i != 0) {
                continue;
            }
            tempList.add(i);
            getFactorsHelper(list, tempList, n / i, i);
            tempList.remove(tempList.size() - 1);
        }
    }
}