Combination Sum III - Video Solutions

Problem Overview: You must pick exactly k distinct numbers from 1..9 so their sum equals n. Each number can be used once, and the result should include all valid combinations without duplicates.

Approach 1: Backtracking (O(2^9) time, O(k) space)

This problem naturally fits backtracking. Start from number 1 and recursively build combinations by choosing the next number and reducing the remaining sum. Stop exploring a path when the combination size exceeds k or the sum becomes negative. When the combination length equals k and the remaining sum is 0, record the result. Since the search space only includes numbers 1..9, the recursion tree is small, making the effective time complexity about O(2^9) and space O(k) for the recursion stack and current path.

Approach 2: Iterative with Bitmasking (O(2^9 * 9) time, O(1) space)

You can enumerate every subset of numbers 1..9 using a bitmask from 0 to (1<<9) - 1. Each bit represents whether a number is included in the subset. For each mask, iterate through the bits, count how many numbers are chosen, and compute their sum. If the subset size equals k and the sum equals n, add it to the result. This approach treats the problem like a subset enumeration on an array of numbers and uses a classic bitmasking pattern. Time complexity is O(2^9 * 9) because every mask checks up to nine bits, while space complexity is O(1) excluding the output.

Recommended for interviews: Backtracking is the expected approach. Interviewers want to see how you prune invalid states early (sum exceeded, size exceeded) and generate combinations without duplicates. The bitmasking method demonstrates good understanding of subset enumeration, but backtracking better shows your ability to control the search space and write clean recursive logic.