Factor Combinations - Solution & Explanation

Problem Overview: Given an integer n, return all unique combinations of factors (excluding 1 and n) whose product equals n. Each combination must be in non-decreasing order, and different permutations of the same factors should not appear multiple times.

Approach 1: Recursive Factor Enumeration (Brute Force DFS) (Time: ~O(n log n), Space: O(log n) recursion)

The straightforward approach tries every possible factor from 2 up to n. For each valid divisor i, add it to the current path and recursively search for combinations that multiply to n / i. The recursion naturally builds factor chains like [2, 2, 3] for 12. To avoid duplicates, the recursive call continues from the same factor i rather than restarting from 2. This keeps combinations sorted and prevents permutations like [3,2,2]. The approach explores many unnecessary candidates, which increases the search space.

Approach 2: Backtracking with Square Root Pruning (Time: ~O(n log n), Space: O(log n))

The optimized solution uses backtracking and only checks divisors up to sqrt(n). If i divides n, two factors are discovered: i and n / i. You append i to the current combination and recursively continue factoring n / i. Each time a valid factor is found, the pair [current factors..., i, n/i] forms a complete combination. Because recursion always continues from the current factor, results remain sorted and duplicates are avoided. The sqrt(n) bound significantly reduces unnecessary checks.

This solution is essentially a depth‑first search over the factor space. The recursion tree depth stays small because the value shrinks quickly after each division. Concepts from DFS and recursion make the implementation concise.

Recommended for interviews: The square‑root bounded backtracking approach. Interviewers expect you to recognize that factors come in pairs and that checking beyond sqrt(n) is redundant. Starting with a brute force recursive enumeration shows understanding of the search space, but pruning with sqrt(n) demonstrates algorithmic optimization and familiarity with backtracking patterns.