1. Backtracking

Intuition

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.

Algorithm

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.

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

Time & Space Complexity

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

• Space complexity: $O(\log (n))$

Where $n$ is the input integer n.

---

2. Iterative DFS

Intuition

The iterative approach uses an explicit stack instead of recursion. Each stack entry contains the current list of factors being built. We pop a state, extract its last factor, and try all valid ways to split it into two smaller factors.

This approach creates new factor lists for each branch rather than modifying and restoring a single list, which simplifies the logic but uses more memory.

Algorithm

1. Initialize a stack with [n] and an empty result list.
2. While the stack is not empty:
   • Pop a factor list and extract its last element as lastFactor.
   • Determine the starting point: 2 if empty, otherwise the last remaining factor.
   • For each i from the starting point up to sqrt(lastFactor):
     • If i divides lastFactor, create a new list with the remaining factors plus i and lastFactor/i.
     • Push this new list onto the stack and add it to the result.
3. Return the result list.

class Solution {
    public List<List<Integer>> getFactors(int n) {

        final List<List<Integer>> ans = new LinkedList<>();
        final Stack<LinkedList<Integer>> stack = new Stack<>();
        stack.push(new LinkedList<>(new LinkedList<>(Arrays.asList(n))));

        while (!stack.isEmpty()) {
            final LinkedList<Integer> factors = stack.pop();
            final int lastFactor = factors.removeLast();
            
            for (int i = factors.isEmpty() ? 2 : factors.peekLast(); i <=  lastFactor / i; ++i) {
                if (lastFactor % i == 0) {
                    // Add i and lastFactor / i.
                    LinkedList<Integer> newFactors = new LinkedList<>(factors);
                    newFactors.add(i);
                    newFactors.add(lastFactor / i);
                    stack.push(newFactors);
                    ans.add(new LinkedList<>(newFactors));
                }
            }
        }

        return ans;
    }
}

Time & Space Complexity

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

• Space complexity: $O(n \cdot \log (n))$

Where $n$ is the input integer n.

---

Common Pitfalls

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.