Combination Sum III

The key idea

Build combinations by trying digits 1 to 9 in strictly increasing order. Because each number is picked at most once and always larger than the last, every combination is generated exactly once with no duplicates. Prune a branch as soon as the running sum exceeds n or not enough digits remain.

Problem

Find all valid combinations of k numbers that sum up to n, subject to two rules: only the numbers 1 through 9 may be used, and each number is used at most once in a combination.

Return a list of all the valid combinations. The list must not contain the same combination twice, and the numbers within each combination may be listed in any order.

Constraints

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

Examples

Input: k = 3, n = 7 Output: [[1,2,4]]

Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]]

Input: k = 4, n = 1 Output: []

Complexity

Time: O(C(9,k) * k) Space: O(k)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →