Combination Sum III
Problem Statement
Find all valid combinations of exactly k numbers that sum to n using only numbers 1 through 9. Each number may be used at most once, and each valid combination should appear once.
Input
Two integers: k, the exact number of values to choose, and n, the required sum.
Output
A list of combinations where each combination has exactly k distinct numbers from 1..9 and sums to n.
Constraints
- •
2 <= k <= 9 - •
1 <= n <= 60
Examples
Example 1
k = 3, n = 7
[[1,2,4]]Example 2
k = 3, n = 9
[[1,2,6],[1,3,5],[2,3,4]]Example 3
k = 4, n = 1
[]Learning Objectives
- Combine the start-index template with both a count constraint and a sum constraint.
- Use **1..9** as a fixed ordered candidate range without an input array.
- Prune branches using remaining count, minimum possible sum, and maximum possible sum.
- Stop candidate loops when the current value exceeds the remaining sum.
Intuition
Pattern Recognition
This is the combination start-index pattern on a fixed universe 1..9. Order does not matter, and each number can be used at most once, so after choosing value, the next recursive call starts at value + 1.
The difference from plain Combinations is that a path must satisfy two goals at the same time: exactly k numbers and sum n. That makes pruning especially powerful. If the remaining slots cannot be filled from the remaining numbers, or if even the smallest possible fill is too large, or if even the largest possible fill is too small, the branch can stop before exploring children.
Common mistakes
- ×Adding a path when the sum is correct but the path length is not **k**.
- ×Allowing number **10** or reusing a number because the start value was not advanced.
- ×Missing the low-sum and high-sum bounds, which makes the recursion tree noisier than needed.
- ×Stopping only when remaining becomes negative instead of using the exact count constraint as well.
Algorithm Explanation
State
Each frame stores start, the next number allowed from 1..9, remaining, the sum still needed, and path, the numbers chosen so far. The remaining count is k - path.size().
Recursion tree
For k = 3, n = 9, the root chooses 1, then tries second choices 2, 3, and higher. Branch [1,2] needs 6, so choosing 6 completes [1,2,6]. Branch [1,3] needs 5, so [1,3,5] is added. Branch [1,4] would need 4, but future numbers must be greater than 4, so it is pruned. After backtracking, root choice 2 can produce [2,3,4]. Larger roots are pruned by the minimum possible sum for the remaining slots.
Pruning
If no slots remain, add the path only when remaining == 0. If there are not enough numbers left between start and 9, return. Compute the smallest sum obtainable by taking the next needed numbers and the largest sum obtainable by taking the largest needed numbers from 1..9. If remaining is outside that range, return. During the loop, break when value > remaining.
Algorithm
- Start DFS with start = 1, remaining = n, and an empty path.
- Let needed = k - path.size().
- If needed == 0, add the path only when remaining == 0.
- Prune if too few numbers remain, if the minimum possible fill exceeds remaining, or if the maximum possible fill is below remaining.
- Loop value from start through 9, breaking when value > remaining.
- Choose value, recurse with value + 1 and remaining - value, then unchoose it.
Solutions
Solution: Bounded start-index DFS over 1 through 9
The fixed range lets us add stronger bounds than the generic combination template. Before branching, compare the remaining target against the smallest and largest sums that can be made with the required number of future picks.
Step-by-step
- Begin from value 1 with the full target remaining.
- At each frame, calculate how many more numbers are needed.
- If no numbers are needed, record the path only when the remaining sum is 0.
- Prune when there are too few values left, when the next smallest values already exceed the remaining sum, or when the largest possible values cannot reach it.
- Try each value from start to 9, recurse with value + 1, and remove the value after returning.
O(C(9, k) * k)
O(k)
The search considers combinations of the fixed 1..9 range and copies each valid path of length k. With 9 fixed, the practical cost is constant.
Java implementation
Dry Run
Sample input
k = 3, n = 9. Track remaining and the exact count as the DFS moves forward through 1..9.
| depth | start | choice | path and sum | action |
|---|---|---|---|---|
| 0 | 1 | 1 | [1], remaining 8 | choose 1, need two more numbers |
| 1 | 2 | 2 | [1,2], remaining 6 | choose 2 |
| 2 | 3 | 6 | [1,2,6], remaining 0 | needed count reached, add combination |
| 1 | 2 | 3 | [1,3], remaining 5 | choose 3 |
| 2 | 4 | 5 | [1,3,5], remaining 0 | needed count reached, add combination |
| 1 | 2 | 4 | [1,4], remaining 4 | prune because next number must exceed 4 |
| 0 | 1 | 2 | [2], remaining 7 | choose 2 from root |
| 1 | 3 | 3 | [2,3], remaining 4 | choose 3 |
| 2 | 4 | 4 | [2,3,4], remaining 0 | needed count reached, add combination |
| 0 | 1 | 4 | [4], remaining 5 | prune because the two smallest following numbers exceed remaining |
The valid combinations are found only when both constraints meet at the same leaf: exactly three numbers and remaining sum 0.
Interview Tips
Emphasise the double constraint. A sum of 0 is not enough unless the path has exactly k numbers, and a path of length k is not enough unless the sum is exact. The min and max possible sum bounds are a strong way to demonstrate pruning maturity on a small search space.
Likely follow-ups
- How would the solution change for choosing from **1..m** instead of **1..9**?
- How would you return combinations in descending lexicographic order?
- How would you count the combinations without storing them?
- How would you adapt the bounds if candidates came from an arbitrary sorted array?
Similar Problems
Key Takeaways
- Exact count and exact sum must both be checked at the leaf.
- The range **1..9** uses the same start-index no-reuse rule as combinations.
- Minimum and maximum possible sums prune impossible branches early.
- Advancing to **value + 1** prevents reuse and keeps combinations increasing.