Combinations

Difficulty: Medium Source: NeetCode

Problem

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.

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

Example 2: Input: n = 1, k = 1 Output: [[1]]

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

Prerequisites

Before attempting this problem, you should be comfortable with:

• Subsets — generating all subsets is the generalization of this problem (subsets of size k)
• Backtracking — making choices, recursing, and undoing choices
• Combinatorics — C(n, k) counts the number of valid outputs

1. Brute Force

Intuition

Use Python’s itertools.combinations to directly generate all C(n, k) combinations of k elements chosen from [1, n]. This is a valid approach in an interview if you’re allowed standard library usage, but understanding the underlying mechanism is the real goal here.

Algorithm

1. Create a range [1, 2, ..., n].
2. Use itertools.combinations(range(1, n+1), k) to get all combinations.
3. Convert to list of lists and return.

Solution

from itertools import combinations

def combine_builtin(n, k):
    return [list(c) for c in combinations(range(1, n + 1), k)]


print(combine_builtin(4, 2))
# [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(combine_builtin(1, 1))
# [[1]]

Complexity

• Time: O(C(n,k) * k) — C(n,k) combinations, each of length k
• Space: O(k) — recursion depth (excluding output)

2. Backtracking

Intuition

Start from number 1 and at each step decide which number to pick next. We always pick numbers in increasing order (start the next pick from current + 1), which naturally avoids duplicates like [2,1] and [1,2] both appearing. We stop recursing once the current combination has k elements. A useful pruning trick: if there aren’t enough numbers left to fill k spots, bail early.

Algorithm

1. Define backtrack(start, current).
2. If len(current) == k: append a copy to results and return.
3. For i from start to n:
   • Pruning: if n - i + 1 < k - len(current), there aren’t enough numbers left — break.
   • Append i, recurse with start = i + 1, pop i.

Solution

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

    def backtrack(start, current):
        if len(current) == k:
            result.append(list(current))
            return
        # pruning: need (k - len(current)) more numbers, have (n - i + 1) available
        for i in range(start, n + 1):
            if n - i + 1 < k - len(current):
                break  # not enough numbers remaining
            current.append(i)
            backtrack(i + 1, current)
            current.pop()

    backtrack(1, [])
    return result


print(combine(4, 2))
# [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(combine(1, 1))
# [[1]]
print(combine(5, 3))
# [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

Complexity

• Time: O(C(n,k) * k) — C(n,k) valid combinations, each costs O(k) to copy
• Space: O(k) — maximum recursion depth is k

Common Pitfalls

Iterating up to n but forgetting + 1 in range. range(start, n) stops at n-1; you need range(start, n + 1) to include n itself.

Missing the pruning condition. Without pruning, combine(20, 10) explores many dead-end branches. The check n - i + 1 < k - len(current) short-circuits these: if remaining numbers are fewer than remaining spots needed, break early.

Appending current instead of list(current). Classic backtracking pitfall — always copy the list before appending to results.