Combinations (LeetCode 77)

The problem

Given two integers n and k, return every way to choose k distinct numbers from 1, 2, …, n. A combination is a set, so [1,2] and [2,1] are the same and must appear once.

Input:  n = 4, k = 2
Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

There are C(4, 2) = 6 ways to pick 2 numbers out of 4.

How to think about it

Start with brute force. Generate every subset of 1..n (2ⁿ of them) and keep only those of size k. For n = 20, k = 2 that’s about a million subsets to find 190 answers. Wasteful.

The key insight: this is Subsets, but you only record at depth k and stop there. Use the same start index so each combination is built in increasing order and appears exactly once. The difference is the base case: record when len(path) == k, and return instead of going deeper. That cuts the tree off at depth k instead of building every subset.

Why increasing order works. Any set of k numbers has exactly one increasing arrangement. Forcing path to grow only with numbers larger than the last one picked means each set has exactly one path in the tree. No duplicate checks needed.

Which pattern is this? Backtracking with a start index. The tell is “choose k items, order doesn’t matter”. A cheap extra prune: if there aren’t enough numbers left to fill the path (n - i + 1 < k - len(path)), stop the loop early. The code below doesn’t need it to be correct, but it’s a good thing to mention.

Approach

1. bt(start, path): if path has k numbers, record a copy and return.
2. Otherwise, for each i from start to n: append i, recurse with i + 1, pop.
3. Call bt(1, []).

Solution

def combine(n, k):
    res = []
    def bt(start, path):
        if len(path) == k: res.append(path[:]); return   # depth k: a full combination
        for i in range(start, n + 1):
            path.append(i); bt(i + 1, path); path.pop()  # only larger numbers after i
    bt(1, []); return res
# combine(4, 2) -> 6 combinations ([1,2],[1,3],[1,4],[2,3],[2,4],[3,4])

Dry run

On n = 4, k = 2:

The [4] node is a dead end: nothing larger than 4 is left. That’s the branch the “not enough numbers left” prune would skip.

Complexity

• Time: O(k·C(n, k)). There are C(n, k) leaves, each copied in O(k). Internal nodes are bounded by the same order.
• Space: O(k) extra. The recursion depth and path never exceed k.

Edge cases and pitfalls

• k = n gives one combination, [1..n]. k = 0 gives [[]].
• Range off by one. Numbers go from 1 to n inclusive, so the loop is range(start, n + 1) and the first call is bt(1, []).
• Recursing with start + 1 instead of i + 1 produces repeated numbers and duplicates.
• Generating permutations instead. If you use a used array and no start, you’ll get [1,2] and [2,1]. Combinations need the start index.

Related problems

• Subsets (LeetCode 78): the same tree, but every node is recorded.
• Combination Sum (LeetCode 39): the stopping rule becomes “remaining target hits zero”.
• Letter Combinations of a Phone Number (LeetCode 17): fixed depth again, one level per digit.