Combination Sum III: Backtracking with Fixed Size

Find all valid combinations of k numbers that sum up to n such that only digits 1 through 9 are used, and each digit is used at most once. Return a list of all possible valid combinations.

This is LeetCode 216: Combination Sum III. Unlike Combination Sum where you pick from an arbitrary list with unlimited reuse, and Combination Sum II where candidates can repeat, here the candidate pool is fixed (digits 1 to 9), each digit is used at most once, and the combination must contain exactly k numbers. The fixed-size constraint adds an extra layer of pruning that makes this problem surprisingly clean.

Why this problem matters

Combination Sum III is one of the best problems for learning how constraints simplify backtracking. You already know the choose-explore-unchoose template from Combinations and the sum-target pattern from Combination Sum. This problem combines both: you need exactly k numbers, and they must sum to n. The two constraints work together to prune the search tree aggressively.

The problem also teaches you to think about pruning from multiple angles. You can prune when a digit exceeds the remaining sum. You can also prune implicitly through the fixed-size requirement, because once you have picked k numbers, you stop immediately and check whether the sum matches. Both of these keep the recursion tree small even though the digit pool goes up to 9.

The key insight

Pick digits in increasing order (1, 2, 3, ..., 9) to avoid duplicates. At each recursion level, try the next digit starting from one above the last digit you picked. This guarantees every combination is generated in sorted order, so you never produce [2,1,4] and [1,2,4] as separate results.

The algorithm has two base cases. When the combination reaches length k, check if the remaining sum is 0. If yes, record the combination. If not, return immediately. There is no point exploring further because adding more digits would exceed k.

For pruning, if the current digit i exceeds the remaining sum, break. Since digits are tried in order, every digit after i is even larger, so none of them can work either. This single check eliminates large sections of the tree.

The backtracking solution

def combinationSum3(k: int, n: int) -> list[list[int]]:
    result = []

    def backtrack(start, combo, remaining):
        if len(combo) == k:
            if remaining == 0:
                result.append(combo[:])
            return
        for i in range(start, 10):
            if i > remaining:
                break
            combo.append(i)
            backtrack(i + 1, combo, remaining - i)
            combo.pop()

    backtrack(1, [], n)
    return result

Let's break this down.

The outer function initializes the result list and kicks off the recursion starting from digit 1 with an empty combination and the full target n as the remaining sum.

Inside backtrack, the first check is the length. When len(combo) == k, we have picked enough numbers. If remaining == 0, the combination sums to n exactly, so we record a copy. Either way, we return. This is the fixed-size constraint in action: once you reach k numbers, you stop.

The for loop tries digits from start up to 9. The guard if i > remaining triggers a break. Since we iterate digits in ascending order, if digit i already exceeds what we need, no larger digit can help.

After the guard, we append digit i (choose), recurse with i + 1 and reduced remaining (explore), and pop it off (unchoose). Passing i + 1 ensures each digit is used at most once, and picking in order avoids duplicate combinations.

Visual walkthrough

Let's trace through the algorithm with k=3 and n=7. We need exactly 3 digits from 1 to 9 that add up to 7. Watch how the pruning eliminates most branches quickly.

The key observation is how fast the tree collapses. After finding [1,2,4] in Step 5, every other branch hits the i > remaining guard and gets pruned. The fixed-size constraint (len(combo) == k) means we never explore beyond 3 levels deep, and the sum constraint cuts off branches where digits are too large. Together, these two constraints make the actual work much smaller than the theoretical search space of all subsets of {1,...,9}.

How this differs from other Combination Sum problems

The fixed candidate pool and size constraint make Combination Sum III the cleanest of the three. No sorting needed (digits are already in order). No duplicate handling needed (all digits are unique). The only additions are the k check and the fact that the loop goes from start to 9 instead of iterating over a candidates array.

Complexity analysis

Time is O(C(9, k)), which is the number of ways to choose k digits from 9. For k=3 this is C(9,3)=84. In practice, the i > remaining pruning means we visit far fewer nodes than 84. The upper bound is small because the digit pool is capped at 9.

Space is O(k) for the recursion stack and the current combination. The maximum recursion depth is k, and the combination holds at most k elements. Output space is separate and proportional to the number of valid combinations.

The building blocks

This problem is built from three core reusable pieces that CodeBricks drills independently.

Backtracking template (choose-explore-unchoose)

The same skeleton that powers Combination Sum, Combinations, and Combination Sum II:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)
        backtrack(state)
        undo_choice(choice)

In Combination Sum III, make_choice is combo.append(i) and undo_choice is combo.pop(). The recursion uses i + 1 to enforce the "each digit at most once" rule.

Pruning by remaining sum

When the next candidate exceeds what you still need, skip it and everything after it:

if i > remaining:
    break

This pattern appears in every combination sum variant. It relies on candidates being in sorted order (which digits 1 to 9 naturally are).

Fixed-size constraint

When the combination reaches the required length, check immediately and return:

if len(combo) == k:
    if remaining == 0:
        result.append(combo[:])
    return

This is the key difference from Combination Sum I and II. The return after the length check prevents the recursion from going deeper than k levels, which dramatically reduces the search space.

Edge cases

Before submitting, check these:

• k=1: The answer is just [[n]] if n is between 1 and 9, and [] otherwise. Single digit must equal the target.
• n too large for k digits: The maximum sum of k digits is 9 + 8 + 7 + ... (the k largest). For k=2, max is 9+8=17. If n=18 and k=2, return [].
• n too small for k digits: The minimum sum of k digits is 1 + 2 + 3 + ... (the k smallest). For k=3, min is 1+2+3=6. If n=5 and k=3, return [].
• k=9: You must use all digits 1 through 9. The only valid n is 1+2+...+9=45. Any other value returns [].
• Multiple valid combinations: For k=3 and n=9, valid results are [[1,2,6], [1,3,5], [2,3,4]]. The algorithm finds all of them by exploring all branches.

From understanding to recall

You see how the backtracking tree works. The i + 1 prevents digit reuse, the i > remaining prunes large digits, and the len(combo) == k check stops recursion at the right depth. The logic is clean and the code is short.

But can you write it from scratch in under two minutes? That is the interview challenge. The most common mistakes under pressure are forgetting the break when i > remaining, using i instead of i + 1 in the recursive call, or returning without checking remaining == 0 in the base case. These are not conceptual problems. They are recall problems.

Spaced repetition fixes recall. You practice writing the backtracking template with the fixed-size constraint and the remaining-sum pruning from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "find k numbers summing to n" and the code flows out without hesitation.

The backtracking template, remaining-sum pruning, and fixed-size constraint are three of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Combination Sum - Unlimited reuse from a list of distinct candidates. Compare the structure to see how the fixed-size constraint simplifies things here.
• Combination Sum II - Each candidate used once, but candidates can repeat. Requires sorting and same-level duplicate skipping, which Combination Sum III avoids entirely.
• Combinations - Choose k numbers from 1 to n without a sum constraint. The closest structural sibling to this problem.

CodeBricks breaks Combination Sum III into its backtracking template, remaining-sum pruning, and fixed-size constraint building blocks, then drills them independently with spaced repetition. You type the skeleton and the guards from scratch until they are automatic. When a constrained backtracking problem shows up in your interview, you do not think about it. You just write it.