LeetCode #77 Medium

Combinations

Return every possible combination of k numbers chosen from the range 1 to n.

backtrackingrecursioncombinatorics

02

Intuition

💡

The natural first draft loops from 1 to n at every level of the recursion, and it looks right until you read the output: for n=4, k=2 you get both [1,2] and [2,1]. You have written a permutation generator. Order does not matter in a combination, so those are the same answer counted twice, and no amount of checking afterwards is a fix — you are already paying k! times too much work. The repair is one parameter: pass a start index, and have each level loop from start rather than from 1. A child that picks i recurses with start = i+1, so it can never look back at i or anything below it. That forces every path to come out strictly increasing, and here is the invariant — each set of k numbers has exactly one increasing arrangement, so a generator that only produces increasing paths produces each combination exactly once. Duplicates are not filtered out; they are made unreachable.

03

Approach

1

Carry a start index, not a fresh range

The recursive helper takes the smallest number it is still allowed to use. The top-level call passes 1; a level that picks value i recurses with i+1. This single parameter is the difference between combinations and permutations, and it is why you should be suspicious of any backtracking solution over an unordered result that does not carry one.

2

Record when the path reaches length k

The base case is purely a length check: once the path holds k numbers it is a complete combination, so copy it into the results and return. Copy it — appending the path object itself stores a reference that the very next pop will mutate, and you end up with a list of identical empty lists. This is the most common silent bug in every backtracking problem, not just this one.

3

Prune branches that cannot reach length k

If only three numbers remain in the range but you still need four slots, that entire subtree is dead. Cap the loop at n - (k - len(path)) + 1 and those branches are never entered. For n=20, k=16 this turns a visibly slow solution into an instant one, and the reasoning is worth internalising: prune on the constraint you can already prove will fail, not after it does.

04

Solution & live demo

python

▶1class Solution:
▶2    def combine(self, n: int, k: int) -> list[list[int]]:
▶3        res, path = [], []
▶4 
▶5        def backtrack(start: int) -> None:
▶6            if len(path) == k:
▶7                res.append(path[:])
▶8                return
▶9            # only enough numbers left to still fill k slots
▶10            need = k - len(path)
▶11            for i in range(start, n - need + 2):
▶12                path.append(i)
▶13                backtrack(i + 1)
▶14                path.pop()
▶15 
▶16        backtrack(1)
▶17        return res

05

Edge cases

k equals n

Exactly one combination exists — the whole range in increasing order — and the forward-only start index produces it naturally.

k equals 1

Each number forms its own single-element combination, so the answer is n lists of length one.

k greater than n

No combination is possible; the loop bound goes negative, the recursion never reaches depth k, and an empty list falls out without a special case.

k equals 0

The base case fires immediately at depth 0, correctly returning a single empty combination [[]].

06

Complexity

Time

O(C(n,k) * k)

Space

O(k)

C(n,k) paths are produced and each costs O(k) to copy; the recursion stack is only k deep, and the output list itself is not counted as auxiliary space.