Combination Sum

Combination Sum

What is this problem about?

The Combination Sum interview question asks you to find all unique combinations of numbers from a given set of candidates that sum up to a target value. A crucial rule in this problem is that you can use the same candidate number an unlimited number of times. The resulting list of combinations must not contain duplicate sets (though the sets can contain the same number multiple times).

Why is this asked in interviews?

This is a core Backtracking interview pattern used by companies like Meta, Google, and Amazon. It tests a candidate's ability to explore a state space using recursion. Interviewers look for how you handle the "unlimited use" constraint and how you prevent duplicate combinations in your result list. It also evaluates your understanding of recursion pruning—stopping the search once the current sum exceeds the target.

Algorithmic pattern used

The problem is solved using Backtracking. You traverse a decision tree where at each step you have two choices:

1. Include the current candidate in the combination and stay at the same candidate (allowing for unlimited use).
2. Skip the current candidate and move to the next one. This "Pick or Skip" approach, combined with a sorting step at the beginning, allows for a clean and efficient search.

Example explanation

Candidates: [2, 3, 6, 7], Target: 7

1. Start with 2.
2. Path 1: 2, 2, 2, 2 (Sum 8 > 7, Stop).
3. Path 2: 2, 2, 3 (Sum 7, Success! Add [2, 2, 3] to results).
4. Path 3: 2, 3, 2 (This is the same as [2, 2, 3]. To avoid this, we only consider candidates at or after the current index).
5. Path 4: 7 (Sum 7, Success! Add [7] to results). Final result: [[2, 2, 3], [7]].

Common mistakes candidates make

• Duplicate Combinations: Generating [2, 3, 2] and [2, 2, 3] as separate answers. This is usually fixed by passing the current index to the recursive call.
• Missing Base Cases: Forgetting to return when the sum equals the target or when the sum exceeds the target.
• Not Backtracking: Forgetting to remove the last element from the current combination before returning from a recursive call (the "undo" step).

Interview preparation tip

Always draw the recursion tree for a small example. It helps you visualize how the index moves forward and how the "unlimited reuse" is implemented by not incrementing the index when you pick a number.