# LeetCode 216: Combination Sum III

## Problem Restatement

We are given two integers:

```python
k
n
```

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

Rules:

| Rule | Meaning |
|---|---|
| Number range | Only numbers `1` through `9` may be used |
| Reuse | Each number can be used at most once |
| Combination size | Each combination must contain exactly `k` numbers |
| Combination sum | The numbers must add up to `n` |
| Duplicates | The answer must not contain duplicate combinations |

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

| Item | Meaning |
|---|---|
| Input | Integers `k` and `n` |
| Output | List of valid combinations |
| Candidate numbers | `1` to `9` |
| Exact length | Every combination must have length `k` |
| Exact sum | Every combination must sum to `n` |

Example function shape:

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

## Examples

Example 1:

```python
k = 3
n = 7
```

The valid combination is:

```python
[1, 2, 4]
```

because:

```text
1 + 2 + 4 = 7
```

Answer:

```python
[[1, 2, 4]]
```

Example 2:

```python
k = 3
n = 9
```

Valid combinations:

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

Answer:

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

Example 3:

```python
k = 4
n = 1
```

We need four positive distinct numbers from `1` to `9`.

The smallest possible sum of four numbers is:

```text
1 + 2 + 3 + 4 = 10
```

So no answer exists.

Answer:

```python
[]
```

## First Thought: Generate All Choices

The numbers are only:

```python
[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:

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

This means we can produce:

```python
[1, 2, 4]
```

but never separately produce:

```python
[2, 1, 4]
```

So every combination appears once.

## Backtracking State

We need three pieces of state:

| State | Meaning |
|---|---|
| `start` | Smallest number we are allowed to choose next |
| `path` | Current partial combination |
| `remaining` | Sum still needed |

Example:

```python
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:

```python
k = 3
n = 7
```

Start:

```text
path = []
remaining = 7
start = 1
```

Choose `1`:

```text
path = [1]
remaining = 6
start = 2
```

Choose `2`:

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

Choose `3`:

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

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

Backtrack.

Choose `4` instead:

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

Length is `3` and remaining sum is `0`.

Add:

```python
[1, 2, 4]
```

Continue searching, but no other combination works.

Final answer:

```python
[[1, 2, 4]]
```

## Pruning

Backtracking can stop early when a branch cannot work.

Basic pruning:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(C(9, k) * k)` | There are at most `C(9, k)` combinations, and copying a valid path costs `O(k)` |
| Space | `O(k)` | Recursion depth and path length are at most `k` |

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

## Implementation

```python
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:

```python
result = []
```

Create the current combination:

```python
path = []
```

The backtracking function receives:

```python
start
remaining
```

`start` prevents reuse and duplicates.

`remaining` tracks how much sum is still needed.

When the path has exactly `k` numbers:

```python
if len(path) == k:
```

we only keep it if the sum is correct:

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

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

Try candidates:

```python
for x in range(start, 10):
```

Stop if the candidate is already too large:

```python
if x > remaining:
    break
```

Choose the number:

```python
path.append(x)
```

Explore the next state:

```python
backtrack(x + 1, remaining - x)
```

Undo the choice:

```python
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:

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

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

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

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

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `k = 3, n = 7` | Standard single-answer case |
| `k = 3, n = 9` | Multiple valid combinations |
| `k = 4, n = 1` | Impossible small sum |
| `k = 3, n = 15` | Several combinations |
| `k = 9, n = 45` | Uses all numbers exactly once |