254. Factor Combinations

Question

Numbers can be regarded as the product of their factors.

• For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Algorithm

A similar to combination sum question.

First I used bottom up method to get the product from 1, but got TLE when the number is quite big;

So I checked the standard answer and turn to bottom down use backtracking.

Code

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (n < 2) {
            return res;
        }
        helper(res, n, 2, new ArrayList<>());
        return res;
    }
    
    private void helper(List<List<Integer>> res, int n, int index, List<Integer> list) {
        if (n == 1 && list.size() > 1) {
            res.add(new ArrayList<>(list));
        }
        for (int i = index; i <= n; i++) {
            if (n % i == 0) {
                list.add(i);
                helper(res, n/i, i, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

• Space complexity: output: O(n), the space for saving the Internal products: O(log(n))
• Time complexity: For the number of solutions, according to this, can be considered as O(n). And inside the loop to find the next n, we do the n/I each time, the time is O(n^0.5). So in total it's O(n^1.5).