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 should contain factors greater than 1 and appear in non‑decreasing order.

Approach 1: Factor Enumeration + Recursive Backtracking (O(sqrt(n) * k) time, O(k) space)

The natural way to generate factor combinations is backtracking. Start from the smallest factor (2) and iterate upward while the current factor divides n. When a valid divisor i is found, append it to the current path and recursively continue searching for factors of n / i. This builds combinations incrementally while maintaining non‑decreasing order by always starting the next search from i. Each recursion explores deeper factor splits until the remaining value becomes 1 or no further divisors exist.

The key pruning step limits iteration to factors up to sqrt(n). If i divides n, the complementary factor n / i automatically forms a valid pair. That pair can be appended directly to the current path to produce a valid combination without exploring redundant permutations. This significantly reduces the search space compared to testing all integers up to n.

This pattern is a classic use of backtracking: maintain a temporary list, try a candidate factor, recurse on the reduced number, then backtrack by removing the factor. The recursion tree naturally enumerates all valid multiplicative partitions. The number of results (k) depends on the factor structure of n, so runtime scales with both divisor checks and generated combinations.

Approach 2: Optimized Backtracking with Start Pointer (O(sqrt(n) * k) time, O(k) space)

A small optimization keeps a start pointer representing the smallest factor allowed in the current recursion level. This prevents permutations like [2,6] and [6,2] from appearing separately. The algorithm iterates from start to sqrt(remaining), checks divisibility, and recurses with the reduced value. Each valid divisor produces two results: the pair itself and deeper decompositions.

The recursion depth is bounded by the number of factors in a combination, so auxiliary space remains proportional to the path length. This method works well for factor partition problems and appears frequently alongside other recursive enumeration techniques like depth-first search and recursion.

Recommended for interviews: Interviewers typically expect the optimized backtracking approach with a start index and a sqrt(n) bound. It demonstrates control over recursion, pruning, and duplicate avoidance. Showing the naive divisor exploration first proves understanding, but the pruned backtracking version shows strong problem‑solving skill.