LeetCode 254: Factor Combinations

Explanation

To solve this problem, we can use a backtracking approach to generate all possible factor combinations of a given number. We start by finding all factors of the input number and then recursively build combinations by multiplying these factors together. We need to ensure that the factors are in non-descending order to avoid duplicates.

Algorithm:

1. Create a helper function that takes the input number, current factor, current combination list, and a list to store all valid combinations.
2. Find all factors of the input number.
3. Start a loop from the current factor until the square root of the input number.
4. For each factor, check if it divides the input number evenly.
5. If the factor is valid, add it to the current combination list and recursively call the helper function with the updated input number, the current factor (to avoid duplicates), updated current combination list, and the list to store all valid combinations.
6. Add the current combination list to the list of valid combinations when we reach a factor greater than the square root of the input number.

Time Complexity:

The time complexity of this approach is O(n * 2^n), where n is the number of factors of the input number.

Space Complexity:

The space complexity is O(n) where n is the number of factors of the input number.

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (n <= 1) return result;
        backtrack(result, n, 2, new ArrayList<>());
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, int n, int start, List<Integer> tempList) {
        for (int i = start; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                tempList.add(i);
                tempList.add(n / i);
                result.add(new ArrayList<>(tempList));
                tempList.remove(tempList.size() - 1);
                backtrack(result, n / i, i, tempList);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}