# LeetCode 77: Combinations

## Problem Restatement

We are given two integers:

```python
n: int
k: int
```

We need to return all possible combinations of `k` numbers chosen from the range:

```python
1, 2, 3, ..., n
```

The order of combinations in the answer does not matter.

Inside one combination, order also does not define a new result. For example, `[1, 2]` and `[2, 1]` are the same combination.

The official constraints are `1 <= n <= 20` and `1 <= k <= n`. The problem asks for all combinations of `k` numbers chosen from `[1, n]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `n` and `k` |
| Output | A list of all combinations |
| Range | Numbers from `1` to `n` |
| Combination size | Exactly `k` numbers |
| Order | The answer may be returned in any order |

Function shape:

```python
class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        ...
```

## Examples

Example 1:

```python
n = 4
k = 2
```

We need all pairs chosen from:

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

The answer is:

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

Example 2:

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

There is only one number.

The answer is:

```python
[[1]]
```

## First Thought: Brute Force

One simple idea is to generate every subset of `[1, n]`, then keep only the subsets whose length is `k`.

For each number, we make two choices:

1. Take it.
2. Skip it.

Code shape:

```python
class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        ans = []
        path = []

        def dfs(x: int) -> None:
            if x == n + 1:
                if len(path) == k:
                    ans.append(path.copy())
                return

            path.append(x)
            dfs(x + 1)
            path.pop()

            dfs(x + 1)

        dfs(1)
        return ans
```

This works, but it explores all subsets.

There are `2^n` subsets.

Since `n` can be `20`, this is still possible, but we can do better by generating only combinations of size `k`.

## Key Insight

A combination can be built from left to right in increasing order.

For example, with `n = 4` and `k = 2`, once we choose `1`, the next number can only be chosen from:

```python
2, 3, 4
```

This avoids duplicates.

We never generate `[2, 1]`, because after choosing `2`, we only look to the right.

So the recursive state only needs two things:

| State | Meaning |
|---|---|
| `start` | The smallest number we are allowed to choose next |
| `path` | The current combination being built |

When `len(path) == k`, we have one complete combination.

## Algorithm

Start with:

```python
ans = []
path = []
```

Define a recursive function:

```python
backtrack(start)
```

At each call:

1. If `path` already has length `k`, copy it into `ans`.
2. Otherwise, try every number `x` from `start` to `n`.
3. Add `x` to `path`.
4. Recursively choose the next number from `x + 1`.
5. Remove `x` from `path` before trying the next choice.

The important line is:

```python
backtrack(x + 1)
```

That makes every combination increasing, so duplicates are avoided naturally.

## Pruning

We can avoid useless recursive calls.

Suppose we still need:

```python
remain = k - len(path)
```

numbers.

If we choose the next number as `x`, there must be at least `remain - 1` numbers after `x`.

So the largest valid starting choice is:

```python
n - remain + 1
```

Therefore, the loop can be:

```python
for x in range(start, n - remain + 2):
```

The `+2` appears because Python `range` stops before the end.

For example:

```python
n = 4
k = 2
path = []
remain = 2
```

The first number can only be:

```python
1, 2, 3
```

It cannot be `4`, because after choosing `4`, no number remains to complete a pair.

## Correctness

The algorithm only appends a result when `len(path) == k`.

Every appended result therefore contains exactly `k` numbers.

The recursive call always moves from `x` to `x + 1`, so every path is strictly increasing. That means every number in one path is chosen from `[1, n]`, and no number is repeated.

Every valid combination can be written in increasing order:

```python
[a1, a2, ..., ak]
```

where:

```python
1 <= a1 < a2 < ... < ak <= n
```

The recursion can choose `a1` in the first level, then `a2` in the second level, and so on. Since each next call starts after the previous number, this exact combination will be reached.

No combination is produced twice, because each combination has only one increasing order. The algorithm only generates increasing paths, so there is only one possible recursive route to each result.

Therefore, the algorithm returns all valid combinations exactly once.

## Complexity

There are:

```python
C(n, k)
```

valid combinations.

For each completed combination, we copy a list of length `k`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(C(n, k) * k)` | There are `C(n, k)` results, and copying each result costs `k` |
| Space | `O(k)` extra | The recursion path has length at most `k` |
| Output space | `O(C(n, k) * k)` | The returned answer stores all combinations |

The output itself is large, so any correct solution must spend at least this much space to return the result.

## Implementation

```python
class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        ans = []
        path = []

        def backtrack(start: int) -> None:
            if len(path) == k:
                ans.append(path.copy())
                return

            remain = k - len(path)

            for x in range(start, n - remain + 2):
                path.append(x)
                backtrack(x + 1)
                path.pop()

        backtrack(1)
        return ans
```

## Code Explanation

We store final combinations in:

```python
ans = []
```

The current partial combination is:

```python
path = []
```

The recursive function receives the next smallest candidate:

```python
def backtrack(start: int) -> None:
```

When the path reaches size `k`, we copy it:

```python
if len(path) == k:
    ans.append(path.copy())
    return
```

The copy matters. Without `.copy()`, every result would point to the same mutable list.

Then we compute how many more numbers are needed:

```python
remain = k - len(path)
```

The loop uses pruning:

```python
for x in range(start, n - remain + 2):
```

This avoids choosing a number too large to complete the combination.

Then we choose `x`:

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

Search deeper:

```python
backtrack(x + 1)
```

Then undo the choice:

```python
path.pop()
```

This undo step lets the next loop iteration reuse the same `path` cleanly.

## Testing

Since LeetCode accepts any order, tests should compare sorted results.

```python
def normalize(x):
    return sorted([tuple(row) for row in x])

def run_tests():
    s = Solution()

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

    assert normalize(s.combine(1, 1)) == normalize([
        [1],
    ])

    assert normalize(s.combine(3, 3)) == normalize([
        [1, 2, 3],
    ])

    assert normalize(s.combine(5, 1)) == normalize([
        [1],
        [2],
        [3],
        [4],
        [5],
    ])

    assert len(s.combine(5, 3)) == 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 4, k = 2` | Main example |
| `n = 1, k = 1` | Smallest valid input |
| `n = 3, k = 3` | Must choose every number |
| `n = 5, k = 1` | Single-number combinations |
| `n = 5, k = 3` | Checks result count |