• 1 <= n <= 20
• 1 <= k <= n
• Numbers are drawn from the range [1, n], never 0
• Each number may appear at most once in a given combination
• Output size is C(n, k), which peaks near k = n/2

The natural first thought is that this is Subsets with a size filter — generate the power set, keep the entries of length k. That is correct, and looking at why it is wasteful leads directly to the real technique.

With n = 20 the power set has 2²⁰ ≈ 1,048,576 subsets. If k = 2, only C(20,2) = 190 of them survive. More than a million candidates are built to keep fewer than two hundred.

def combine(n, k):
    return [s for s in all_subsets(range(1, n + 1)) if len(s) == k]

The waste is not just the ratio. It is when the failure is detected. A subset of size 7 is only rejected after all seven decisions are made — even though it was doomed the moment it exceeded k. The filter runs at the leaves, and the search happily builds entire branches that could never contribute.

That observation generalises far beyond this problem: checking validity at the leaf is always worse than not generating the invalid branch at all. Everything in this section is an application of it.

There are two separate ways a naive search goes wrong here, and they need different fixes.

First, wrong length. Paths shorter or longer than k are useless.

Second, and more interesting, duplicates. If at every level you may choose any of the n numbers, the search produces [1,2] and also [2,1]. Those are the same combination, so one must be suppressed. Filtering them afterwards means sorting each result and deduplicating — expensive, and it means generating k! copies of every answer just to throw away all but one.

The elegant fix handles the second problem structurally.

Every combination has exactly one representation in increasing order. The set {3,1,2} can be written six ways, but only [1,2,3] is sorted.

So decide in advance to build only sorted paths. Then each combination can be produced by exactly one route through the decision tree, and duplicates become impossible rather than merely detectable.

Enforcing it requires almost nothing: when the last number chosen was i, the next number must be greater than i. Pass a start index down the recursion and never look backwards.

That is the whole trick, and it is worth stating as a principle because it recurs constantly: to avoid generating duplicates, define a canonical ordering for each answer and only ever build answers in that form.

The skeleton is the choose-explore-un-choose rhythm from Subsets, with the choice space narrowed by the start index.

def combine(n, k):
    result = []
    path = []

    def build(start):
        if len(path) == k:
            result.append(list(path))     # complete: snapshot a copy
            return

        for num in range(start, n + 1):
            path.append(num)              # CHOOSE
            build(num + 1)                # EXPLORE — only larger numbers
            path.pop()                    # UN-CHOOSE

    build(1)
    return result

The version above still explores branches that cannot possibly succeed. With n = 5 and k = 4, starting a path at 4 leaves only the numbers 4 and 5 — two candidates for a combination needing four. The recursion dutifully explores and fails.

The check is arithmetic. If the path holds len(path) numbers, it still needs k - len(path) more, and the numbers from num to n provide n - num + 1 candidates. Once the supply falls short, every remaining iteration is doomed:

def build(start):
    if len(path) == k:
        result.append(list(path))
        return

    needed = k - len(path)
    # stop as soon as fewer than 'needed' numbers remain
    for num in range(start, n - needed + 2):
        path.append(num)
        build(num + 1)
        path.pop()

The upper bound n - needed + 2 is the largest starting number that still leaves needed values available. This does not change the complexity — the output size dominates — but it eliminates a great deal of pointless recursion on larger inputs, and recognising the opportunity is what interviewers are watching for.

Six combinations, matching C(4,2). Every one is increasing, and no set was produced twice — not because duplicates were filtered, but because the search could not construct them.

Three problems in this section share one skeleton and differ only in the choice space at each level. Holding the comparison in mind is worth more than memorising any one of them:

The start index is precisely the mechanism that says "order does not matter here". Its presence or absence is the first thing to decide when you meet an unfamiliar enumeration problem.

Recognition signals: choose k of n, how many ways to select, all groups of size k, all committees, all hands of cards — anything where selecting a group is asked for and rearranging that group does not produce a new answer.

Train the reflex: when order does not matter, pick a canonical ordering and generate only that. Deduplicating afterwards means doing k! times too much work and then throwing most of it away.