Combination Sum III

Explanation & Solution

Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used
Each number is used at most once

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Input: k = 3, n = 7

Output: [[1,2,4]]

Explanation: 1 + 2 + 4 = 7. There are no other valid combinations.

Constraints

2 <= k <= 9
1 <= n <= 60

Approach

Subsets pattern

1. Set Up Backtracking

Create an empty result array to collect valid combinations
Begin recursion from start = 1 with an empty current array and remaining = n

2. Base Case — Correct Length Reached

When current.length === k, check if remaining === 0
If so, the current combination uses exactly k numbers that sum to n — add it to result
Return regardless, since we cannot add more numbers

3. Iterate Through Digits 1-9

Loop from start to 9 to ensure each number is used at most once and combinations are generated in increasing order
If the current number i exceeds remaining, break early — all subsequent numbers are even larger

4. Choose and Explore

Push i onto current and recurse with start = i + 1 and remaining - i
After recursion, pop i from current (backtrack) to try the next candidate

5. Return All Valid Combinations

After all paths are explored, result contains every unique combination of k numbers from 1-9 that sum to n

Key Insight

The search space is small (only digits 1-9), so the algorithm is very efficient despite being exponential in theory
By iterating from start onward, each combination is generated in strictly increasing order, which naturally avoids duplicates

Time

**O(C(9, k))** — at most choosing k elements from 9

Space

O(k) for the recursion stack depth

Solution Code

Combination Sum II

Letter Combinations of a Phone Number