DSA problem
Combination Sum III
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, and each number is used at most once. The solution set must not contain duplicate combinations, and the answer may be returned in any order.
This is a constrained variant of the subset-sum family. Compared to Combination Sum II, the candidate pool is fixed (1..9) and the answer has the extra fixed-cardinality constraint path.length == k. The constrained pool means there are at most 2^9 = 512 subsets to consider, so worst-case effort is tiny.
The natural approach is backtracking over 1..9 with a start index that walks forward (so each number is used at most once and ordering is canonical). Two pruning conditions accelerate things dramatically: stop early when the remaining target becomes negative, and stop early when the remaining slots cannot be filled (i.e., when fewer than k - path.length candidates remain). The latter prune lets us tighten the loop upper bound to 9 - (k - path.length) + 1.
When path.length == k and remaining == 0, we snapshot the path into results. Otherwise we iterate the loop with i running from start to that pruned upper bound, choose i, recurse with start = i + 1 and remaining = n - i, then un-choose. The combination of fixed pool and double-pruning makes this one of the cleanest backtracking templates to write.
Examples
k = 3, n = 7[[1,2,4]]k = 3, n = 9[[1,2,6],[1,3,5],[2,3,4]]k = 4, n = 1[]Constraints
- 2 <= k <= 9
- 1 <= n <= 60
- Only numbers 1 through 9 are used in each combination.
- Each number is used at most once.
- The solution set must not contain duplicate combinations.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.