Problem statement
Choose exactly k different numbers from 1..9 so their sum is n. Return every valid value combination once. A number cannot be reused, and changing the order of the same chosen numbers does not create another answer.
Both conditions matter: the sum must match and the list must have exactly k elements. For k=3,n=7, [1,6] has the correct sum but is not a valid answer.
The published constraints are 2≤k≤9 and 1≤n≤60. Here n is the target sum, not the number of available values. The candidate universe always has nine numbers.
Constraints & requirements
- CONTRACT
- LeetCode: 2≤k≤9 and 1≤n≤60. Both count and sum must match. Advance to the next digit in BOTH take and skip branches; preserve saved answers while restoring the shared path.
Examples 3 test cases
Example 1 Case 1
- Input
k=3; n=7- Output
[[1,2,4]]
1+2+4=7 with exactly three distinct allowed digits.
Example 2 Case 2
- Input
k=3; n=9- Output
[[1,2,6],[1,3,5],[2,3,4]]
The three value combinations are unique; rearrangements are not additional answers.
Example 3 Case 3
- Input
k=4; n=1- Output
[]
Even the smallest four distinct digits sum to 10, which already exceeds 1.
Hints Optional
01Hint 1
A sum of n with fewer or more than k digits is not an answer.
02Hint 2
Choose or skip the current digit, retiring it in either branch.
03Hint 3
Before searching, compare the remaining sum with the smallest and largest sums possible using exactly the remaining slots.
How to think before coding
Compare the three Combination Sum contracts before choosing a template:
| Problem | Candidate source | Reuse | Required count |
|---|---|---|---|
| Combination Sum | Given distinct positive array | Allowed | Any count |
| Combination Sum II | Given array, possibly duplicate values | Each index once | Any count |
| Combination Sum III | Fixed values 1..9 | Each value once | Exactly k |
For III, process one allowed digit at a time. We may take it or skip it, but both branches advance to the next digit. That makes the shared path increasing, so [1,2,4] can be produced but its rearrangement [4,1,2] cannot.
Track remaining rather than repeatedly summing the path. Also track how many values are still needed. A promising sum with too few available digits is still impossible.
Brute force: check all subsets
There are only 2^9=512 subsets of 1..9. A baseline checks every subset, counts selected values and calculates its sum, keeping those that match both conditions. This is correct and practical for the fixed domain.
Backtracking is useful here because it teaches how to reject impossible prefixes before building every full subset. It is a pruning improvement, not a claim that a nine-element baseline is unusable or that every combination problem needs a complicated optimization.
Intuition: sum and count constrain the same suffix
Let next be the smallest digit we have not decided yet. Let slots=k−path.size().
Before branching, check:
- Are at least
slotsdigits left innext..9? - Is the remaining sum at least the sum of the smallest
slotsavailable digits? - Is it at most the sum of the largest
slotsavailable digits?
For next=3, slots=2, the smallest possible suffix is 3+4=7. If remaining=6, no descendant can help; do not enter it.
Deriving the sum bounds
The smallest suffix is the arithmetic sequence next,next+1,...,next+slots−1. Its sum is slots × (2×next+slots−1) / 2.
The largest suffix is 9,8,...,10−slots, with sum slots × (19−slots) / 2. Check that enough digits remain before using these bounds. This ensures those largest digits are actually in the available range.
These guards are safe because all candidates are distinct and positive. They would need reconsideration for a different problem with zeros, negatives or reuse.
Why does the size base case return even on failure?
Once the path contains k digits, appending another would violate the count rule. Save only if remaining==0, then return either way. Reaching a target sum alone is not the base case for this question.
Algorithm
- Start with an empty path,
next=1andremaining=n. - At size k, save a list copy only when remaining is zero; then return.
- Reject exhausted digits, an overshot target, insufficient available digits or impossible sum bounds.
- Take next if it fits: append it, recurse using
next+1, and remove it on return. - Skip next: recurse using
next+1without changing remaining or the path.
Java solution
This preserves the take/skip structure of the local practice solution. It adds explicit suffix bounds and uses remove(size−1) for Java 17 compatibility.
import java.util.*;
class Solution {
public static List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
chooseDigits(k, n, 1, new ArrayList<>(), result); // Start before choosing any of 1..9.
return result; // Every saved combination contains exactly k distinct digits.
}
private static void chooseDigits(int k, int remaining, int next,
List<Integer> path, List<List<Integer>> result) {
if (path.size() == k) { // Reaching the requested size is not sufficient by itself.
if (remaining == 0) result.add(new ArrayList<>(path)); // Save an independent valid answer.
return; // No branch may use more than k numbers.
}
if (next > 9 || remaining < 0) return; // No available digit, or an overshot positive target.
int slots = k - path.size(); // How many numbers are still required?
if (10 - next < slots) return; // Too few distinct digits remain in next..9.
int minimum = slots * (2 * next + slots - 1) / 2; // next + ... + (next+slots-1).
int maximum = slots * (19 - slots) / 2; // 9 + 8 + ... using exactly slots digits.
if (remaining < minimum || remaining > maximum) return; // Even the best possible suffix cannot fit.
if (next <= remaining) { // All available numbers are positive; a larger one cannot help.
path.add(next); // Take this digit once.
chooseDigits(k, remaining - next, next + 1, path, result); // Retire it in the child.
path.remove(path.size() - 1); // Restore this caller's prefix after its take subtree.
}
chooseDigits(k, remaining, next + 1, path, result); // Skip it; do not change the remaining sum.
}
public static void main(String[] args) {
System.out.println(combinationSum3(3, 7)); // [[1, 2, 4]]
System.out.println(combinationSum3(3, 9)); // [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
System.out.println(combinationSum3(4, 1)); // []
}
}The main method prints the single combination for (3,7), the three combinations for (3,9), and an empty result for (4,1).
Illustrated dry run
Use k=3,n=7. The pruned search below is complete: it includes the rejected full path [1,2,3], the successful [1,2,4], every undo and the remaining bound-pruned sibling subtrees.

Read the text transcript
Follow the Java, step by step
Example: k = 3, n = 7
What to track: Each call owns remaining and next; path/result are shared. Both take and skip retire next. Minimum/maximum bounds use exactly the still-needed slots. This is the complete pruned traversal.
-
Enter with three slots
Java operationint slots = k - path.size();Statenext=1; remaining=7; path=[]; slots=3; minimum=6; maximum=24Seven lies between 1+2+3 and 7+8+9, so the root may contain an answer.
-
Take 1, then take 2
Java operationchooseDigits(k, remaining - next, next + 1, path, result);Statechild (next=2, remaining=6, path=[1]); then (next=3, remaining=4, path=[1,2])Increasing next in both children prevents using 1 or 2 again and avoids order-only duplicates.
-
Reject the full but wrong-size-sum candidate
Java operationif (remaining == 0) result.add(new ArrayList<>(path));Statetake 3 → next=4; remaining=1; path=[1,2,3]; size=k; no answer savedExactly three values have been selected, but they sum to 6 rather than 7. The size base case returns even on failure.
-
Undo 3 and skip it
Java operationpath.remove(path.size() - 1);Stateresumed caller: next=3, remaining=4, path=[1,2]; skip child: next=4, remaining=4The caller keeps its original remaining sum. Its skip branch changes only next, not remaining or the prefix.
-
Take 4 and save the valid combination
Java operationresult.add(new ArrayList<>(path));Statenext=5; remaining=0; path=[1,2,4]; size=k; result=[[1,2,4]]Both required conditions now hold. A list copy survives when the caller removes 4.
-
Prune after skipping 4
Java operationif (remaining < minimum || remaining > maximum) return;Statenext=5; remaining=4; path=[1,2]; slots=1; minimum=5Every remaining digit is at least 5. One positive digit cannot fill a gap of 4.
-
Undo 2; skip-2 branch cannot fit
Java operationchooseDigits(k, remaining, next + 1, path, result);Statenext=3; remaining=6; path=[1]; slots=2; minimum=3+4=7This entire sibling subtree is impossible. It is skipped by the bound rather than by pretending a valid child was explored.
-
Undo 1 and finish at the root
Java operationif (remaining < minimum || remaining > maximum) return;Stateroot skip child: next=2; remaining=7; path=[]; slots=3; minimum=2+3+4=9The only remaining root subtree cannot reach 7. The saved answer remains, while the shared path ends empty.
Final result: [[1,2,4]]; all caller prefixes are restored after their branches.
When following a return, restore the caller’s path and read the caller’s original remaining value. The child received a smaller integer; it did not overwrite the parent’s local variable.
Why it works
Legal paths: Every taken digit lies in 1..9. Both branches retire that digit, so selected values are distinct and increasing.
Correct saves: A path is saved only when its length is k and its remaining sum is zero. Every saved answer therefore satisfies both requirements.
Complete search: Any valid combination makes exactly one take/skip choice for each digit. The algorithm follows that unique decision path unless a bound proves that no completion exists. Such a proof cannot remove a valid answer.
No duplicates: There is only one increasing take/skip representation of a chosen set. We do not need a HashSet to remove permutations afterward.
Complexity and alternative approaches
For explanation, let m be the size of the candidate universe; in this exact problem, m=9. Let R be the number of answers.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Enumerate bitmasks and scan each subset | O(m × 2^m + kR) | O(m), excluding answers | Small, exhaustive baseline |
| Take/skip with suffix bounds | O(2^m + kR) upper bound | O(m), excluding answers | Constant-time checks can discard whole subtrees |
Both searches are bounded by a small fixed universe here. Returning R independent length-k lists needs O(kR) space and copy work.
The path holds at most k values, but the recursion can also contain skip calls. Its depth is bounded by m, not just by k. Do not label total auxiliary space O(k) while ignoring those frames.
Common mistakes
- Saving
[1,6]for k=3 just because its sum is 7. - Passing next unchanged in the take branch, accidentally allowing reuse.
- Changing remaining in the skip branch.
- Saving the shared list without copying it.
- Returning after the first saved combination;
(3,9)has three. - Applying the minimum bound before checking that enough digits remain.
- Describing the exponential factor using target n rather than the nine available digits.