Combination Sum III

Combination Sum III

What is this problem about?

In the Combination Sum III interview question, you must find all combinations of k numbers that sum up to a target n, using only numbers from 1 to 9. Each number can be used at most once. This problem is more constrained than the others, as it limits both the available pool of numbers and the size of the combination.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask this Backtracking interview pattern to see if you can handle multiple constraints simultaneously (sum constraint and count constraint). It's also a good test of efficiency, as the search space is quite small (subsets of {1..9}), allowing candidates to focus on clean code and early pruning.

Algorithmic pattern used

The core pattern is Backtracking with two stopping conditions:

1. The combination has k numbers.
2. The current sum equals or exceeds n. Because the numbers are strictly increasing (1 to 9), the search is naturally ordered, making it easier to avoid duplicate combinations.

Example explanation

k = 3, n = 7

1. Try 1:
   • Try 2:
     • Try 3: Sum is 1+2+3 = 6. (Too small, only 3 numbers allowed).
     • Try 4: Sum is 1+2+4 = 7. (Success! Add [1, 2, 4]).
     • Try 5: Sum 1+2+5 = 8. (Too big, Stop).
2. Try 2:
   • Try 3: Sum is 2+3+?. Next number must be 2. But we can't reuse numbers. No other combinations will work for k=3 and n=7.

Common mistakes candidates make

• Loop range: Forgetting that you can only use numbers up to 9.
• Off-by-one: Not handling the "exactly k numbers" condition correctly.
• Inefficient pruning: Not stopping the loop when the current number is already greater than the remaining sum needed.

Interview preparation tip

Since the pool is limited to 1-9, the total number of combinations is very small (2^9 = 512). This is a great problem to practice the "Bitmask" approach as an alternative to backtracking.