216. Combination Sum III

216

MediumBacktrackingBacktracking over a bounded candidate set (1..9)Combination backtracking with fixed size and pruning

Combination Sum III

Find all valid combinations of k distinct numbers chosen from 1 through 9 that sum to n. Each number may be used at most once and each combination must be unique.

Open official problem prompt ↗

In plain English

List every unordered group of exactly k different digits (1 through 9) whose values add up to n.

Picture it like this

Like choosing k different coins from a tray holding one each of coins 1..9 so their total equals n; once you pass a coin you cannot come back to it, keeping every group in increasing order.

Example

Input: k = 3, n = 7
Output: [[1,2,4]]
Why: 1 + 2 + 4 = 7 uses exactly 3 distinct digits from 1..9; no other size-3 subset of distinct digits sums to 7.

Constraints

2 <= k <= 91 <= n <= 60Each number 1..9 used at most onceAll combinations must be unique

Pattern lesson

See the pattern, then code

Combination backtracking with fixed size and pruning

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Iterate candidates in increasing order and pass a start index so each number is only considered once, which automatically avoids permuted duplicates.

New words, made simpleKnow these before the algorithm

Combination: An unordered selection where [1,2,4] and [4,2,1] count as the same.
Start index: The smallest digit still available, enforcing increasing picks so no duplicates arise.
Pruning: Cutting off a branch early once it cannot possibly succeed, e.g. when the digit already exceeds the remaining sum.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force all subsets of 1..9

Works because the pool is tiny but explores many irrelevant sizes and sums.

Enumerate all 512 subsets, keep those of size k summing to n.

Time O(2^9 * 9)Space O(1)

Best choiceBacktracking with start index and sum pruning

Explores only promising, correctly sized, non-duplicated combinations.

Grow combinations in increasing order, stopping branches when the count hits k or a digit overshoots the remaining sum.

Time O(C(9, k) * k)Space O(k)

The rule we keep true

Invariant

path always holds a strictly increasing sequence of digits whose sum is n minus remaining.

Why this is correct

Reasoning

Because digits are drawn in strictly increasing order via the start index, every combination is generated exactly once; accepting only when len(path)==k and remaining==0 guarantees both the size and sum constraints hold.

The algorithm in three movesSay these aloud before coding

1Recurse carrying the next start digit and the remaining sum

path=[1], rem=6

2When the path holds k numbers, accept it only if remaining is 0

path=[1,2], rem=4

3Loop digits from start to 9

path=[1,2,4], rem=0 -> record

4Prune: stop the loop once a digit exceeds the remaining sum

5Choose the digit, recurse from digit+1, then undo

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readstart=1, remaining=7

2 · AskAdd digit 1?

3 · Update statepath=[1], rem=6

4 · ResultRecurse from 2

Key takeaway

Digits 1..9 with the chosen combination 1, 2, 4 highlighted.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-10Size and sum gate
Only a path of exactly k numbers with zero remaining is a valid answer.
2
Lines 11-13Candidate loop with prune
Iterate digits from start; break as soon as a digit exceeds remaining since later digits are even larger.
3
Lines 14-16Choose and backtrack
Add digit, recurse from num+1 to keep picks distinct and increasing, then remove it.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n larger than 45 (=1+...+9) yields no combinations
k larger than the number of digits that can sum to n yields empty
Exactly one combination exists, as in k=3, n=7

Common beginner mistakes

Recursing from num instead of num+1, which reuses a digit
Forgetting the remaining==0 check and accepting any size-k path
Omitting the break prune, causing unnecessary work

Check your understanding

Why does recursing from num+1 (not num) matter here but not in problems that allow reuse?

PyPython 3 · solution.py

Optimal

1class Solution:2    def combinationSum3(self, k: int, n: int) -> list[list[int]]:3        res: list[list[int]] = []4        path: list[int] = []56        def backtrack(start: int, remaining: int) -> None:7            if len(path) == k:8                if remaining == 0:9                    res.append(path[:])10                return11            for num in range(start, 10):12                if num > remaining:13                    break14                path.append(num)15                backtrack(num + 1, remaining - num)16                path.pop()1718        backtrack(1, n)19        return res

Time complexityO(C(9, k) * k)Optimized

Space complexityO(k)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftAdobe

Combination Sum III

Combination Sum III

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking