Combinations

The duplicate-ordering trap is the whole problem: [1, 2] and [2, 1] represent one selection, not two. Build every path in increasing order, and the duplicate disappears before it reaches the result.

Read the contract before choosing the pattern

You are given n and k. The candidates are the integers from 1 through n, and the task is to return every selection containing exactly k distinct values.

For n = 4 and k = 2, the result family is:

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

The order of the outer result does not matter. The order inside each combination does matter only as a representation: we will store each path in increasing order so that every unordered selection has one canonical form.

There are no target sums here, no candidate reuse, and no duplicate values in the input range. That makes this different from Combination Sum variants. The only obligations are:

1. Choose exactly k values.
2. Choose each value at most once.
3. Treat different orderings of the same values as one answer.

The direct solution is a backtracking search:

• Keep a mutable path.
• Choose the next value only from a forward range.
• Decrease the number of values still needed.
• Copy complete paths into the result.
• Stop exploring a branch when the remaining range cannot fill the quota.

That is the combinations backtracking pattern in its cleanest form.

Choose canonical paths instead of repairing duplicates

A tempting baseline is to generate every subset of [1, n], keep the subsets of size k, and perhaps deduplicate them afterward. That explores roughly 2^n subsets even though the contract asks for only the k-element ones.

Another poor direction is to generate ordered selections. For n = 4, k = 2, that search may produce both:

[1, 2]
[2, 1]

Deduplication can repair the output, but it cannot recover the work already spent exploring the wrong search space.

The structural clue is stronger:

Choose exactly k items from an ordered finite range, use each item at most once, and ignore selection order.

Represent each combination canonically as a strictly increasing path. Once the path contains 1, the next choice can be 2, 3, or 4, but never 1 again and never a value smaller than 1. After choosing 3, only 4 remains available.

This gives every combination one construction path:

[1, 3]    yes
[3, 1]    never constructed

The algorithm does not generate duplicates and then clean them up. It makes duplicate orderings impossible.

You can also express the search as binary include/skip decisions: include the current number or skip it. That formulation is valid, but the loop-based version exposes the important boundary directly: “which values may be the next choice?” For this problem, that makes the state and pruning easier to inspect in an interview.

Derive the state and transitions

Let the recursive function be:

backtrack(start, remaining)

Each parameter answers a specific obligation:

• path: the current partial combination.
• start: the smallest value that may be chosen next.
• remaining: how many more values are required.

The recursive contract is:

backtrack(start, remaining) explores every valid completion of the current path using values from start through n, choosing exactly remaining more values.

The success case

When remaining == 0, the path has received all required values. Store a copy and stop:

if remaining == 0:
    result.append(path.copy())
    return

The copy matters because path is shared mutable state. The algorithm will later pop values from it. Storing the list object itself would make previously stored answers change as the search continues.

The transition

Suppose the next candidate is i.

1. Append i to path.
2. Recurse from i + 1, because values must increase.
3. Decrease remaining by one.
4. Pop i so the caller sees its original path again.

In symbols:

path.append(i)
backtrack(i + 1, remaining - 1)
path.pop()

The pop is not cleanup in the casual sense. It restores the state required to explore the next sibling branch.

The capacity bound

At a state beginning at start, the available values are:

n - start + 1

If fewer than remaining values are available, completion is impossible:

if n - start + 1 < remaining:
    return

There is also a useful loop bound. If you choose i as the next value, you still need remaining - 1 values after it. Therefore, i cannot be so large that the suffix is too short.

The largest legal next value is:

n - remaining + 1

For example, with n = 4 and remaining = 2, the first choice may be at most 3. Choosing 4 would leave no value for the second position.

Because Python's range excludes its upper bound, the implementation uses:

range(start, n - remaining + 2)

That includes n - remaining + 1.

Prove the invariant and uniqueness

A passing example is not a correctness argument. The useful proof comes from the state invariant.

At every call, path is strictly increasing, contains distinct values in [1, n], and has exactly k - remaining values.

Initialization

The initial call is:

backtrack(1, k)

The path is empty, so it is increasing, contains no invalid values, and has k - k = 0 selected values.

Preservation

Assume the invariant holds before choosing i.

• i is at least start, so it is larger than the last value in path when the path is nonempty.
• The recursive call uses i + 1, so every future choice must be larger than i.
• Therefore, the path remains strictly increasing and contains no duplicates.
• The path length increases by one while remaining decreases by one, preserving len(path) = k - remaining.

After the recursive call, path.pop() restores the exact path that existed before this branch. That restoration is what lets the loop try the next candidate without carrying state across branches.

Soundness

A path is emitted only when remaining == 0. By the invariant, it then contains exactly k values. Those values are distinct and lie in [1, n]. Every emitted path is therefore a valid combination.

Completeness

Take any valid combination. It has exactly one increasing representation:

[a1, a2, ..., ak]
where a1 < a2 < ... < ak

At the first level, the loop eventually chooses a1. The recursive call then begins at a1 + 1, so it can choose a2, and so on. Since every valid next value remains inside the loop's legal range, the search eventually constructs the entire combination.

Uniqueness

The next choice is always larger than the previous choice. A path such as [2, 1] is never constructed after [1, 2]; it is disallowed by the start index. Thus each set of values has exactly one increasing construction path.

This is the key distinction between generating combinations and generating permutations. The increasing order is not cosmetic formatting. It is the uniqueness mechanism.

Prune with available capacity

Pruning should come from a proof of impossibility, not from intuition.

Consider n = 4, k = 2.

• At path = [], four values are available and two are needed.
• After choosing 1, values 2, 3, and 4 remain. The search can produce [1, 2], [1, 3], and [1, 4].
• After choosing 3, only 4 remains, so [3, 4] is still possible.
• After choosing 4, no value remains. Since one more value is needed, that branch stops immediately.

The loop bound prevents the last impossible top-level choice. At the first level, 4 is not tried because choosing it would leave fewer than one value for the suffix.

Capacity pruning and loop bounding express the same fact at different points:

available values < values required

The safe rule is simple: prune only when the state mathematically cannot reach the quota.

Pruning removes dead-end calls and reduces wasted traversal. It does not remove output work. If the answer contains C(n, k) combinations, every one of those combinations still has to be created and returned.

Translate the derivation into Python

Here is the interview-ready implementation:

from typing import List


def combine(n: int, k: int) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int, remaining: int) -> None:
        # The quota is filled: materialize this combination.
        if remaining == 0:
            result.append(path.copy())
            return

        # The remaining suffix cannot fill the quota.
        if n - start + 1 < remaining:
            return

        # The upper bound leaves enough values after i.
        for i in range(start, n - remaining + 2):
            path.append(i)
            backtrack(i + 1, remaining - 1)
            path.pop()

    backtrack(1, k)
    return result

Read the code as a sequence of obligations:

• path remembers the current partial answer.
• start prevents reuse and reverse-order duplicates.
• remaining enforces the fixed output size.
• path.copy() freezes a completed answer.
• i + 1 moves the future search forward.
• path.pop() restores the caller's state.
• n - remaining + 2 prevents choices that leave too few values afterward.

Common bugs are predictable:

• Use backtrack(i, ...) instead of backtrack(i + 1, ...): the same value can be reused.
• Forget pop(): values from one branch leak into sibling branches.
• Append path instead of path.copy(): every stored answer refers to the same mutable list.
• Use range(start, n + 1): the code explores avoidable dead ends.
• Stop only when len(path) == k but never track capacity: the algorithm remains correct with a broader loop, but it performs unnecessary calls and makes the pruning logic invisible.

Dry-run the mutable state

For n = 4, k = 2, the search begins with:

path = []
start = 1
remaining = 2

A compact trace:

Call state	Action	New path	Next state	Result
start=1, remaining=2	choose 1	[1]	start=2, remaining=1	continue
start=2, remaining=1	choose 2	[1, 2]	remaining=0	emit [1, 2]
return	pop 2	[1]	—	try next sibling
start=2, remaining=1	choose 3	[1, 3]	remaining=0	emit [1, 3]
return	pop 3	[1]	—	try next sibling
start=2, remaining=1	choose 4	[1, 4]	remaining=0	emit [1, 4]
return	pop 4, then pop 1	[]	—	try 2

The next top-level branches begin with 2, then 3, producing [2, 3], [2, 4], and [3, 4].

The important motion is not merely downward recursion. It is downward selection followed by upward restoration:

append
recurse
pop

Every append must have exactly one matching pop after its recursive exploration. When debugging backtracking, trace that pair before inspecting anything more sophisticated.

Complexity and edge-case checks

There are:

C(n, k)

valid combinations. Each completed path contains k values, and path.copy() takes O(k) time. Therefore, the output materialization alone costs:

O(k · C(n, k))

This is more precise than writing only O(C(n, k)), because the algorithm must copy k values for every output.

With capacity-aware pruning, the search avoids branches that cannot finish. The auxiliary working space is:

O(k)

for the mutable path and recursion stack, whose maximum depth is k. The returned result is separate output storage and requires:

O(k · C(n, k))

space.

Under the supplied contract, 1 <= k <= n, so the main boundary cases are straightforward:

• k = 1: return each value as a one-element combination.
• k = n: return one combination containing every value from 1 through n.
• Small n: manually trace the path and verify every append/pop pair.
• k > n: this is outside the stated constraints. If you generalize the function, the initial capacity check should return an empty result.

Before coding, my interview checklist is:

1. Is the output an unordered selection rather than a permutation?
2. Can I represent every answer in increasing order?
3. What is the smallest legal next index?
4. How many values does the current path still need?
5. Can the remaining suffix supply that quota?
6. Am I copying completed paths?
7. Does every mutation have a matching restoration?

The transferable rule is compact: when a problem asks for every fixed-size selection from an ordered finite set, choose the next item only from a forward index, track the remaining quota, and prune only when capacity proves failure. One increasing path per output is the mental model. The code follows from it.