Factor Combinations

Factor Combinations

What is this problem about?

The Factor Combinations interview question (also known as "Get Factors") asks you to find all possible combinations of factors that multiply to a given integer n. The factors must be greater than 1 and less than n. For example, for $n=12$, the valid combinations are [2, 2, 3], [2, 6], [3, 4]. Note that the order of factors in a combination does not matter, so [2, 6] and [6, 2] are considered the same.

Why is this asked in interviews?

Companies like Uber and LinkedIn use this Backtracking interview pattern to evaluate your ability to explore a state space recursively while avoiding duplicates. It’s a mathematical variation of the "Combination Sum" problem. It tests whether you can implement pruning (stopping the search when the product exceeds n) and how you maintain a non-decreasing order of factors to ensure uniqueness in the result set.

Algorithmic pattern used

The primary pattern is Backtracking with a non-decreasing constraint.

1. Recursion: Define a function backtrack(target, start_factor).
2. Iteration: Loop from start_factor up to sqrt(target).
3. Condition: If target % i == 0:
   • Add i to the current combination.
   • Recurse with backtrack(target / i, i). The start_factor for the next call is i to maintain order.
   • Add the final remainder target / i as a combination (to finish the current branch).
   • Backtrack by removing i.

Example explanation

$n = 8$

1. Start at 2. $8 \% 2 == 0$. Combination: [2].
2. Recurse with target = 4, start = 2.
   • $4 \% 2 == 0$. Combination: [2, 2].
   • Target is now 2. Remainder is 2. Valid combination: [2, 2, 2].
   • Backtrack from 2.
3. Finish branch for first 2: [2, 4]. Result: [[2, 2, 2], [2, 4]].

Common mistakes candidates make

• Duplicate sets: Returning both [2, 4] and [4, 2]. This is usually prevented by passing the current factor as the minimum for the next recursive step.
• Including 1 or n: Forgetting that factors must be strictly between 1 and $n$.
• Efficiency: Not stopping the loop at sqrt(target), which leads to redundant checks.

Interview preparation tip

Whenever you need to find unique combinations where order doesn't matter, the "non-decreasing order" rule is the most standard and efficient way to handle de-duplication in backtracking.