Combinations — Solution

Problem

Given two integers n and k, return all possible ways to choose k distinct numbers from the range 1 to n (inclusive). The order of numbers within each combination does not matter — [1, 2] and [2, 1] are the same selection.

• Input: n = 4, k = 2
• Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
• Explanation: Every unique pair that can be drawn from {1, 2, 3, 4}, each listed in ascending order.

Counter-example: [2, 1] is NOT a separate answer — the output contains each unique selection exactly once.

Intuition

At each position you pick a number and recurse to fill the rest, always choosing from numbers strictly larger than the last pick so the same set is never generated twice. The key optimization is that if you've placed m numbers and still need k − m more, starting at any number greater than n − (k − m) is pointless — there wouldn't be enough numbers left to complete the combination. This upper-bound prune cuts many dead branches before they're explored.

Solution — Backtracking with Pruning

Build combinations one number at a time, always picking from numbers larger than the last chosen. Prune branches early when too few numbers remain to reach size k.

1. Start with an empty current list and smallest available number start = 1.
2. When current reaches length k, record a copy and return.
3. Compute remaining = k − len(current) — how many more numbers are needed.
4. Loop num from start to n − remaining + 1 (inclusive) — the pruned upper bound.
5. Append num, recurse with start = num + 1, then pop num to undo the choice.

1def combine(n: int, k: int) -> list[list[int]]:
2    results = []
3    current = []
4
5    def backtrack(start: int) -> None:
6        if len(current) == k:
7            results.append(current[:])  # snapshot before backtracking modifies current
8            return
9        remaining = k - len(current)
10        # no point starting at num if fewer than remaining numbers exist after it
11        for num in range(start, n - remaining + 2):
12            current.append(num)
13            backtrack(num + 1)
14            current.pop()  # undo choice so next iteration starts with a clean slate
15
16    backtrack(1)
17    return results

Time: O(k × C(n, k)) — there are C(n, k) combinations and copying each takes O(k).
Space: O(k) for the recursion stack depth (output storage is not counted).

Complexity Summary

Common Mistakes

• range(start, n) instead of range(start, n + 1) — an off-by-one that silently drops n from every possible combination.
• Appending current instead of current[:] — all entries in results point to the same list object, which ends up empty once backtracking finishes.
• Skipping the pruning upper bound — iterating all the way to n wastes time on recursive calls that can never produce a full combination of size k.
• Calling backtrack(num) instead of backtrack(num + 1) — allowing the same number to be picked again produces multisets (e.g., [1, 1]) instead of combinations.
• Forgetting current.pop() after the recursive call — without undoing the choice, the list keeps growing across all branches and the results are corrupted.

Related Problems

• permutations — same backtracking skeleton but order matters, so every remaining element is eligible at each step rather than only larger ones
• subsets — generate combinations of every size from 0 to n, not just a fixed k
• combination-sum-ii — combinations from a list with duplicate values that must reach a target sum, adding duplicate-skipping logic
• subsets-ii — subsets from a list with repeated elements, same deduplication technique applied during backtracking
• letter-combinations-of-a-phone-number — backtracking over a character alphabet rather than an integer range