Factor Combinations

How it works

To find all unique factor combinations of n, we use backtracking. At each step, we take the last factor in our current list and try to split it into two smaller factors. By only considering factors greater than or equal to the previous one, we avoid generating duplicate combinations like [2, 6] and [6, 2].

The key insight is that if we have a product, we only need to try factors up to the square root of that product. If i divides the product, then both i and product/i are factors, and we recursively continue with product/i.

Steps

1. Start with factors = [n] and an empty result list.
2. In the backtracking function:
   • If factors has more than one element, it represents a valid combination, so add a copy to the result.
   • Pop the last factor (call it lastFactor).
   • Determine the starting point: use 2 if factors is empty, otherwise use the last remaining factor.
   • For each i from the starting point up to sqrt(lastFactor):
     • If i divides lastFactor, push both i and lastFactor/i, recurse, then pop both to backtrack.
   • Restore lastFactor to factors before returning.
3. Return the result list.

Complexity

• Time complexity: O(n^{1.5})

• Space complexity: O(log (n))

Where n is the input integer n.

Things to watch for

Generating Duplicate Combinations

A common mistake is generating duplicate factor combinations like [2, 6] and [6, 2]. To avoid this, always ensure factors are added in non-decreasing order by only considering factors greater than or equal to the previous factor in the current combination.

Including 1 or n as Factors

The problem explicitly excludes 1 and n itself as valid factors. Forgetting this constraint leads to including trivial factorizations like [1, n] or just [n] in the result. Always start factor candidates from 2 and stop before reaching n.

Inefficient Factor Search

Searching for factors up to n instead of sqrt(n) leads to unnecessary iterations. Since factors come in pairs (if i divides n, then n/i also divides n), you only need to check up to the square root of the current product to find all factor pairs efficiently.

from typing import List

class Solution:
    def _backtracking(self, factors: List[int], ans: List[List[int]]) -> None:
        # Got a solution.
        if len(factors) > 1:
            ans.append(factors.copy())

        last_factor = factors.pop()

        i = 2 if not factors else factors[-1]
        while i <= last_factor // i:
            if last_factor % i == 0:
                # Add i and last_factor // i.
                factors.append(i)
                factors.append(last_factor // i)
                self._backtracking(factors, ans)
                # Remove the last 2 elements in factors to restore it after the recursion returns.
                factors.pop()
                factors.pop()
            i += 1

        # Add last_factor back to factors to restore it.
        factors.append(last_factor)

    def getFactors(self, n: int) -> List[List[int]]:
        ans = []
        self._backtracking([n], ans)
        return ans

class Solution {
    void backtracking(vector<int>& factors, vector<vector<int>>& ans) {
        // Got a solution,
        if (factors.size() > 1) {
            ans.push_back(factors);
        }

        const int lastFactor = factors.back();
        factors.pop_back();

        for (int i = factors.empty() ? 2 : factors.back(); i <= lastFactor / i; ++i) {
            if (lastFactor % i == 0) {
                // Add i and lastFactor / i.
                factors.push_back(i);
                factors.push_back(lastFactor / i);
                backtracking(factors, ans);
                // Remove the last 2 elements in factors to restore it after the recursion returns
                factors.pop_back();
                factors.pop_back();
            }
        }

        // Add lastFactor back to factors to restore it.
        factors.push_back(lastFactor);
    }

public:
    vector<vector<int>> getFactors(int n) {
        vector<int> factors = {n};
        vector<vector<int>> ans;
        backtracking(factors, ans);

        return ans;
    }
};