Combination Sum III — InterviewPrepKit

Solving tips

Backtrack over digits 1-9 with a start digit and recurse with d+1 so each digit is used at most once and combinations stay in increasing order.
A leaf counts only when BOTH len(path) == k AND remaining == 0; checking only the sum accepts wrong-length sets.
Break the loop early when d > remaining (digits ascend), and optionally add a slot-capacity window prune: with s slots left, feasible sums lie in [s*start + s(s-1)/2, 9s - s(s-1)/2].
The whole universe is 2^9 = 512 subsets, so complexity is O(C(9,k)*k); pruning is about habit, not survival.

Problem

Find all combinations of exactly k distinct numbers that sum to n, where every number must come from 1 through 9 and each number may appear at most once per combination. Return the list of all such combinations; no combination may appear twice (as a set of numbers), and any output order is acceptable.

Examples

k = 3, n = 7 → [[1,2,4]] — the only trio of distinct digits summing to 7.
k = 3, n = 9 → [[1,2,6],[1,3,5],[2,3,4]] — three valid trios.
k = 4, n = 1 → [] — the smallest 4 distinct digits already sum to 1+2+3+4 = 10 > 1.

Constraints

2 <= k <= 9
1 <= n <= 60

The universe is only the digits 1–9, so the whole search space is 2^9 = 512 subsets — tiny. The problem is a clean sandbox for the backtracking template and its pruning arithmetic rather than a performance fight.

Think about it first

Hint 1

Only digits 1..9, each used at most once. How many subsets of {1,...,9} exist in total? Could you afford to look at every one of them?

Hint 2

Build combinations in increasing order with a start digit, tracking how many numbers you've placed and what remains of n. What two conditions must hold at a leaf for the path to count?

Hint 3

Prune with arithmetic: if the remaining sum is smaller than the next candidate digit, or larger than the sum of the biggest digits you could still take (9 + 8 + ... for the remaining slots), the branch is dead. Stop the loop early since digits ascend.

TL;DR

Backtracking over digits 1–9 with a start digit and sum/slot pruning — O(C(9,k) · k) time, O(k) space; the whole space is at most 2^9 = 512 subsets.

Approach 1 — Brute force: enumerate all 512 subsets

The universe is fixed at nine digits, so just enumerate every subset of {1..9} via a bitmask and keep those with exactly k elements summing to n. A bitmask enumeration treats each integer 0..2^9-1 as a subset: bit i set means digit i + 1 is included.

from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result: List[List[int]] = []
        for mask in range(1 << 9):
            combo = [d for d in range(1, 10) if mask >> (d - 1) & 1]
            if len(combo) == k and sum(combo) == n:
                result.append(combo)
        return result

Complexity: O(2^9 · 9) ≈ 4600 operations — constant, and it genuinely passes. The constraints don’t kill this one; what kills it is that it doesn’t scale (make the universe 1..30 and 2^30 is over a billion) and it teaches nothing reusable — the interviewer wants the pruned search.

Approach 2 — Backtracking with start digit

The insight: build combinations in strictly increasing digit order — each call gets a start digit and only considers start..9 — so every subset is generated exactly once and distinctness is automatic. Track two budgets at once: numbers still to place (k - len(path)) and sum still to reach (remaining). This is textbook backtracking: depth-first extension of a partial solution, undone on return.

from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int, remaining: int) -> None:
            if len(path) == k:
                if remaining == 0:
                    result.append(path.copy())
                return
            for d in range(start, 10):
                if d > remaining:
                    break                 # digits ascend: all later ones overshoot
                path.append(d)
                backtrack(d + 1, remaining - d)
                path.pop()

        backtrack(1, n)
        return result

Walkthrough on k = 3, n = 7:

[1] (rem 6) → [1,2] (rem 4) → [1,2,3] rem 1 ≠ 0, reject; [1,2,4] rem 0 → record; d = 5 > 4 → break.
[1,3] (rem 3) → next digit must be ≥ 4 but 4 > 3 → break. [1,4] (rem 2): 5 > 2 → break. [1,5] (rem 1): 6 > 1 → break. [1,6] (rem 0) has only 2 digits, and its child loop breaks at once (7 > 0), so nothing is recorded there.
[2] (rem 5) → [2,3] (rem 2): 4 > 2 → break. [2,4] (rem 1): break. [2,5] rem 0, length 2 — dead.
[3] (rem 4) → [3,4] rem 0, length 2 — dead; higher starts overshoot.

Result: [[1,2,4]].

Complexity: O(C(9,k) · k) time — the tree visits each of the C(9,k) size-k subsets at most once, copying costs k; O(k) space for path and recursion.

Approach 3 — Add the slot-capacity prune

The insight: you know exactly how many numbers are left to place, and the digits are bounded, so both sides of the branch can be tested arithmetically. With s slots left, the reachable sums from digit d onward lie between d + (d+1) + ... + (d+s-1) (take the s smallest available) and 9 + 8 + ... + (10-s) (take the s largest). If remaining falls outside that window, cut the branch before looping.

from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int, remaining: int) -> None:
            slots = k - len(path)
            if slots == 0:
                if remaining == 0:
                    result.append(path.copy())
                return
            min_reach = slots * start + slots * (slots - 1) // 2   # start, start+1, ...
            max_reach = slots * 9 - slots * (slots - 1) // 2       # 9, 8, ...
            if remaining < min_reach or remaining > max_reach:
                return                    # window prune: branch can never land on 0
            for d in range(start, 10):
                if d > remaining:
                    break
                path.append(d)
                backtrack(d + 1, remaining - d)
                path.pop()

        backtrack(1, n)
        return result

Walkthrough on k = 4, n = 1: first call has slots = 4, min_reach = 4·1 + 6 = 10, and remaining = 1 < 10 → return immediately. The entire search is one arithmetic check — Approach 2 would have descended into [1], [1,2], [1,2,3] before giving up.

Complexity: unchanged asymptotically — O(C(9,k) · k) time, O(k) space — but dead subtrees are now rejected at their root, which is the habit that pays off when the same problem shape appears with a larger universe.

Common pitfalls

Checking remaining == 0 without also checking len(path) == k — k = 3, n = 3 would wrongly accept [1,2] and [3].
Recursing with d instead of d + 1 — digits then repeat, and [1,1,5] sneaks into k=3, n=7.
Off-by-one in the arithmetic-series prune (slots*(slots-1)//2 vs slots*(slots+1)//2) — derive it once from start + (start+1) + … rather than guessing.
Forgetting that n can be up to 60 while the max reachable sum is 9+8+…+1 = 45 — the window prune handles this for free; without it you still terminate, just slower.

Pattern takeaway

When the choice universe is small and bounded (digits, letters, board cells), backtracking’s value isn’t survival — brute force survives too — it’s the pruning discipline: track every budget the problem gives you (count of picks and remaining sum here) and compute the feasible window before descending. “Can the best case still reach the target, and can the worst case avoid overshooting it?” is a reusable prune for every constrained-combination search.