LeetCode 77: Combinations

Problem Restatement

We are given two integers:

n: int
k: int

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

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

Function shape:

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

Examples

Example 1:

n = 4
k = 2

We need all pairs chosen from:

[1, 2, 3, 4]

The answer is:

[
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 3],
    [2, 4],
    [3, 4],
]

Example 2:

n = 1
k = 1

There is only one number.

The answer is:

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

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:

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:

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

Algorithm

Start with:

ans = []
path = []

Define a recursive function:

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:

backtrack(x + 1)

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

Pruning

We can avoid useless recursive calls.

Suppose we still need:

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:

n - remain + 1

Therefore, the loop can be:

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

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

For example:

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

The first number can only be:

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:

[a1, a2, ..., ak]

where:

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:

C(n, k)

valid combinations.

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

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

Implementation

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:

ans = []

The current partial combination is:

path = []

The recursive function receives the next smallest candidate:

def backtrack(start: int) -> None:

When the path reaches size k, we copy it:

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:

remain = k - len(path)

The loop uses pruning:

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

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

Then we choose x:

path.append(x)

Search deeper:

backtrack(x + 1)

Then undo the choice:

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.

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: