Combinations: Backtracking with a Size Constraint

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.

This is LeetCode 77: Combinations, and it connects two ideas you may already know from other backtracking problems. If you have solved Subsets, you know how a start index prevents duplicate selections. If you have solved Combination Sum, you know how a constraint can prune entire branches. Combinations merges both: use a start index to avoid duplicates, and stop building a path once it reaches length k.

For n = 4 and k = 2, the output is [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]].

Why this problem matters

Combinations is the cleanest example of bounded backtracking. In Subsets, every partial path is a valid answer, so you record at every node. In Combination Sum, you record only when a running sum hits zero. In Combinations, you record only when the path length equals k. That single constraint turns a full enumeration into a selective one, and it introduces an optimization that trips people up: you can stop exploring a branch early if there are not enough numbers left to fill the remaining slots.

This "not enough numbers left" pruning is worth learning on its own. It shows up in Combination Sum III (LeetCode 216), where you need exactly k numbers from 1 to 9 that sum to a target. The pruning logic is identical: if the pool of remaining candidates is smaller than the number of slots you still need, abandon the branch.

Once you can write bounded backtracking from scratch, you have a tool that handles any problem asking for "all groups of exactly k items."

The key insight

Think of building a combination as picking numbers one at a time, always moving forward. At each step you ask: "Which number do I add next?" You only consider numbers strictly greater than the last one you picked. That forward-only rule means you never produce [3,1] after already producing [1,3]. It is the same start-index trick from Subsets, applied to the range [1, n] instead of an array.

The algorithm works like this:

1. Start with an empty path and start = 1.
2. For each number from start to n, choose it (append to path), explore (recurse with start = i + 1), and unchoose it (pop).
3. If the path length equals k, record a copy and return.
4. If the remaining numbers (n - i + 1) are fewer than the remaining slots (k - len(path)), skip the rest of the loop.

The backtracking solution

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

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return

        for i in range(start, n + 1):
            if n - i + 1 < k - len(path):
                break

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

    backtrack(1, [])
    return result

Let's break this down.

The outer function initializes result as an empty list, then calls backtrack(1, []). The first argument is the starting number (so you only pick numbers you have not already used), and the second is the combination being built.

Inside backtrack, the base case checks whether the path has reached length k. When it has, you copy the path into result and return. There is no reason to keep adding numbers once you have a complete combination.

The for loop iterates from start to n. Before appending i, the pruning check asks: are there enough numbers left (from i to n) to fill the remaining slots? If n - i + 1 is less than k - len(path), no branch from here can produce a valid combination, so you break.

If the number fits, you append it (choose), recurse with i + 1 (explore numbers after it), and then pop it off (unchoose). Passing i + 1 ensures you never pick the same number twice and never produce duplicate combinations.

Visual walkthrough

Let's trace through the algorithm with n = 4 and k = 2. Watch how the start index moves forward after each pick, and how the pruning cuts the [4] branch.

The key moments are step 5 and step 8. In step 5, after exhausting all combinations starting with 1, the algorithm moves to 2 and only considers numbers after it (3 and 4). In step 8, starting with 4 leaves zero candidates for the second slot, so the branch is abandoned. The total count matches C(4, 2) = 6.

How this compares to Subsets and Combination Sum

The code looks almost identical to both, but the constraint changes the behavior:

If you already know Subsets, Combinations adds one thing: stop recording when the path reaches length k and prune when the remaining pool is too small. The skeleton is exactly the same.

Complexity analysis

Time is O(k * C(n, k)). There are C(n, k) valid combinations, and copying each one into the result takes O(k) time. The recursion visits roughly C(n, k) leaf nodes plus some internal nodes, but the pruning keeps the tree tight. The dominant cost is the C(n, k) copies of length k.

Space is O(k * C(n, k)) for storing all combinations in the result. The recursion stack uses O(k) additional space (the maximum depth equals k). If you ignore the output, the extra space is just O(k).

Edge cases

Before submitting, check these:

• k = 1: Every number from 1 to n is its own combination. Should return [[1], [2], ..., [n]].
• k = n: Only one combination exists: [1, 2, ..., n]. The algorithm picks every number.
• n = 1: If k = 1, return [[1]]. No other value of k is valid given the constraints.
• Large n, small k: n = 20, k = 2 produces C(20, 2) = 190 combinations. The pruning keeps it fast.
• Large k close to n: n = 20, k = 18 produces C(20, 18) = 190 combinations (same as k = 2 by symmetry). The pruning aggressively cuts branches with too few remaining numbers.

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

Bounded backtracking

The standard choose-explore-unchoose skeleton with a size constraint:

def backtrack(start, path):
    if len(path) == k:
        result.append(path[:])
        return

    for i in range(start, n + 1):
        path.append(i)
        backtrack(i + 1, path)
        path.pop()

The only difference from the Subsets skeleton is the base case. Instead of recording at every node, you record only when the path hits a target length. This same bounded pattern appears in Combination Sum III, where you need exactly k numbers summing to a target. The skeleton is identical; only the recording condition changes.

Start-index to avoid duplicates

Passing start = i + 1 in the recursive call ensures you never revisit a number you already decided on. This is the same technique used in Subsets and Combination Sum. Without it, you would generate both [1, 3] and [3, 1], which are the same combination in different orders.

The start-index pattern is the mechanism that turns permutation-style enumeration into combination-style enumeration. Whenever a problem asks for combinations (order does not matter), you need this pattern.

Common mistakes

1. Missing the pruning check. Without n - i + 1 < k - len(path), the algorithm still works but explores far more branches. For n = 20, k = 2, the unpruned version enters many single-element paths that can never grow to length 2. Always prune.

2. Using range(1, n + 1) instead of range(start, n + 1). Starting from 1 every time means you reconsider numbers you already picked. You will get duplicate combinations like [1, 3] and [3, 1], and also combinations with repeated numbers like [2, 2].

3. Forgetting to copy the path. result.append(path) appends a reference. After all the pop() calls, path is empty, and every entry in your result is []. Use path[:] or list(path).

4. Off-by-one in the range. The numbers go from 1 to n inclusive, so the loop must be range(start, n + 1). Using range(start, n) skips n and produces fewer combinations.

From understanding to recall

You understand the recursion tree. You see how the start index prevents duplicates, and how the size constraint stops exploration once a combination is complete. But can you write the combinations solution from scratch in under two minutes?

That is what interviews demand. Bounded backtracking looks simple in a blog post, but under pressure, small details trip people up: off-by-one in the range, forgetting the pruning check, copying the path wrong. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the bounded backtracking skeleton and the pruning condition from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "all combinations of k numbers" and the code flows out without hesitation.

The bounded backtracking pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subsets - The unbounded version of the same pattern. Every node is a valid result instead of only nodes at depth k. Compare the two to see how a single base-case change reshapes the recursion tree.
• Combination Sum - Uses the same choose-explore-unchoose skeleton but with element reuse and a sum constraint instead of a size constraint. Shows how swapping i + 1 for i enables repeated picks.

CodeBricks breaks Combinations into its bounded-backtracking building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.