Combination Sum III - Video Solutions

Problem Overview: You need to generate all unique combinations of k numbers from the range 1–9 such that their sum equals n. Each number can be used at most once, and combinations must contain exactly k numbers.

Approach 1: Backtracking (Time: O(C(9,k)), Space: O(k))

This problem naturally fits backtracking. You build combinations incrementally while exploring numbers from 1 to 9. At each step, append the current number to a temporary list, update the remaining sum, and recursively explore the next numbers. Pruning makes this efficient: stop exploring when the remaining sum becomes negative or the combination length exceeds k. Once the combination length reaches k and the remaining sum is 0, record the result. Since the search space only contains numbers 1..9, the recursion tree is small and predictable. This approach works well for problems involving constrained subsets of an array-like sequence where combinations must satisfy a condition.

The key insight is enforcing increasing order during recursion. When you choose a number i, the next recursive call only considers numbers i+1 through 9. This guarantees uniqueness without additional data structures. The recursion depth never exceeds k, so auxiliary space stays small.

Approach 2: Iterative with Bitmasking (Time: O(2^9 * 9), Space: O(1) extra)

Another way is to enumerate every subset of numbers 1..9 using 9-bit masks. Each mask represents whether a number is included. Iterate from 0 to (1 << 9) - 1, count the number of set bits, and compute the subset sum. If the mask contains exactly k numbers and the sum equals n, convert the mask into the corresponding combination. This method avoids recursion entirely and relies on simple bit operations and iteration.

Bitmasking treats the candidate numbers as a fixed-size set. For each mask, check bits using bitwise operations and build the combination. Since the total number of subsets is only 512, the algorithm runs quickly even with repeated checks. It’s a clean iterative alternative when you want deterministic enumeration instead of recursive exploration.

Recommended for interviews: The backtracking approach is what most interviewers expect. It demonstrates control over recursion, pruning, and combination generation—core skills in backtracking and recursion problems. Bitmasking works because the domain is small, but it doesn’t scale as well conceptually. Showing both approaches signals strong understanding of search-space enumeration.