Combination Sum III
Medium · Backtracking · Array · Backtracking
Problem
Find every combination of exactly k different numbers from 1 to 9 that adds up to n. Each number may be used at most once.
Return the list of all valid combinations, with no combination repeated. The combinations may be returned in any order, and the numbers inside each one in any order.
Examples
Input: k = 2, n = 6 Output: [[1,5],[2,4]]
3 + 3 is not allowed because numbers cannot repeat.
Input: k = 3, n = 8 Output: [[1,2,5],[1,3,4]]
These are the only sets of three different numbers totaling 8.
Input: k = 4, n = 5 Output: []
The four smallest numbers already add up to 1 + 2 + 3 + 4 = 10.
Constraints
- 2 <= k <= 9
- 1 <= n <= 60
Approaches
- Baseline: check all 512 subsets — time O(2^9 · 9), space O(1) beyond the answer
Follow-up
Only 512 sets of distinct numbers exist, so even trying them all is fast; backtracking matters when the range grows. The use cases count the combinations over a range up to 40 (too many to list) and search for a product instead of a sum.
Related problems
Start free on Cariara · Coding problems · System design studio
