LeetCode 216: Combination Sum III

Problem Restatement

We are given two integers:

k
n

We need to find all valid combinations of exactly k numbers that sum to n.

Rules:

The result can be returned in any order. The problem statement defines exactly these conditions: use only numbers from 1 through 9, use each number at most once, and return all unique valid combinations.

Input and Output

Example function shape:

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

Examples

Example 1:

k = 3
n = 7

The valid combination is:

[1, 2, 4]

because:

1 + 2 + 4 = 7

Answer:

[[1, 2, 4]]

Example 2:

k = 3
n = 9

Valid combinations:

[1, 2, 6]
[1, 3, 5]
[2, 3, 4]

Answer:

[[1, 2, 6], [1, 3, 5], [2, 3, 4]]

Example 3:

k = 4
n = 1

We need four positive distinct numbers from 1 to 9.

The smallest possible sum of four numbers is:

1 + 2 + 3 + 4 = 10

So no answer exists.

Answer:

[]

First Thought: Generate All Choices

The numbers are only:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

So we can try all possible subsets.

For each subset:

1. Check if it has exactly k numbers.
2. Check if the sum is n.
3. If both are true, keep it.

This works because the candidate set is small.

But we can write it more directly with backtracking, which builds only possible combinations.

Key Insight

This is a combination search problem.

At each step, we choose the next number.

To avoid duplicates, we always choose numbers in increasing order.

For example, after choosing 2, the next number must come from:

[3, 4, 5, 6, 7, 8, 9]

This means we can produce:

[1, 2, 4]

but never separately produce:

[2, 1, 4]

So every combination appears once.

Backtracking State

We need three pieces of state:

Example:

path = [1, 2]
remaining = 4
start = 3

This means:

• we have already chosen 1 and 2
• we still need sum 4
• the next chosen number must be at least 3

Algorithm

1. Start DFS with:
   • start = 1
   • path = []
   • remaining = n
2. If len(path) == k:
   • If remaining == 0, add a copy of path to the answer.
   • Return.
3. Try every number x from start to 9.
4. If x > remaining, stop the loop because later numbers are even larger.
5. Choose x.
6. Recurse with:
   • start = x + 1
   • remaining = remaining - x
7. Remove x from path.

Walkthrough

Use:

k = 3
n = 7

Start:

path = []
remaining = 7
start = 1

Choose 1:

path = [1]
remaining = 6
start = 2

Choose 2:

path = [1, 2]
remaining = 4
start = 3

Choose 3:

path = [1, 2, 3]
remaining = 1

Length is 3, but remaining sum is not 0, so reject.

Backtrack.

Choose 4 instead:

path = [1, 2, 4]
remaining = 0

Length is 3 and remaining sum is 0.

Add:

[1, 2, 4]

Continue searching, but no other combination works.

Final answer:

[[1, 2, 4]]

Pruning

Backtracking can stop early when a branch cannot work.

Basic pruning:

if x > remaining:
    break

Since numbers are tried in increasing order, once x is too large, every later number is also too large.

We can also prune by count:

if len(path) == k:
    ...

Once we already have k numbers, we should not add more.

Correctness

The algorithm only chooses numbers from 1 through 9.

It passes x + 1 as the next start, so each chosen number is larger than the previous one. Therefore no number is reused, and each combination is generated in strictly increasing order.

Every generated result has exactly k numbers because the algorithm only adds a path to the answer when len(path) == k.

Every generated result sums to n because the algorithm only adds a path when remaining == 0.

Now consider any valid combination. Its numbers can be written in increasing order. The DFS can choose those numbers one by one because each next number is greater than the previous one and remains within 1 through 9. Therefore every valid combination is eventually reached.

Since each combination is generated only in increasing order, duplicates cannot appear.

Thus the algorithm returns exactly all valid combinations.

Complexity

The output list itself can contain many combinations, so output storage is separate from auxiliary space.

Implementation

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

        def backtrack(start: int, remaining: int) -> None:
            if len(path) == k:
                if remaining == 0:
                    result.append(path[:])
                return

            for x in range(start, 10):
                if x > remaining:
                    break

                path.append(x)
                backtrack(x + 1, remaining - x)
                path.pop()

        backtrack(1, n)

        return result

Code Explanation

Create the result list:

result = []

Create the current combination:

path = []

The backtracking function receives:

start
remaining

start prevents reuse and duplicates.

remaining tracks how much sum is still needed.

When the path has exactly k numbers:

if len(path) == k:

we only keep it if the sum is correct:

if remaining == 0:
    result.append(path[:])

The copy path[:] is necessary because path will keep changing during backtracking.

Try candidates:

for x in range(start, 10):

Stop if the candidate is already too large:

if x > remaining:
    break

Choose the number:

path.append(x)

Explore the next state:

backtrack(x + 1, remaining - x)

Undo the choice:

path.pop()

Stronger Pruning Version

We can prune branches using minimum and maximum possible sums.

If we still need need numbers, then the smallest possible sum from start is:

start + (start + 1) + ... + (start + need - 1)

The largest possible sum from 1 through 9 using need numbers is:

9 + 8 + ... + (9 - need + 1)

If remaining is outside this range, the branch cannot succeed.

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

        def backtrack(start: int, remaining: int) -> None:
            need = k - len(path)

            if need == 0:
                if remaining == 0:
                    result.append(path[:])
                return

            if start > 9:
                return

            min_sum = sum(range(start, start + need))
            max_sum = sum(range(10 - need, 10))

            if remaining < min_sum or remaining > max_sum:
                return

            for x in range(start, 10):
                if x > remaining:
                    break

                path.append(x)
                backtrack(x + 1, remaining - x)
                path.pop()

        backtrack(1, n)

        return result

The first version is usually enough because the search space contains only nine numbers.

Testing

def normalize(result):
    return sorted(result)

def run_tests():
    s = Solution()

    assert normalize(s.combinationSum3(3, 7)) == [[1, 2, 4]]

    assert normalize(s.combinationSum3(3, 9)) == [
        [1, 2, 6],
        [1, 3, 5],
        [2, 3, 4],
    ]

    assert s.combinationSum3(4, 1) == []

    assert normalize(s.combinationSum3(3, 15)) == [
        [1, 5, 9],
        [1, 6, 8],
        [2, 4, 9],
        [2, 5, 8],
        [2, 6, 7],
        [3, 4, 8],
        [3, 5, 7],
        [4, 5, 6],
    ]

    assert s.combinationSum3(9, 45) == [[1, 2, 3, 4, 5, 6, 7, 8, 9]]

    print("all tests passed")

run_tests()