TL;DR
Backtracking with a start value and a “not enough numbers left” prune — O(C(n,k) · k) time, O(k) space beyond the output.
Approach 1 — Brute force: filter all subsets
Enumerate every subset of {1..n} with a bitmask and keep the ones of size k. A bitmask enumeration reads each integer 0..2^n - 1 as a subset: bit i set means the number i + 1 is in.
from typing import List
def combine(n: int, k: int) -> List[List[int]]:
result: List[List[int]] = []
for mask in range(1 << n):
if bin(mask).count("1") != k:
continue
combo = [v for v in range(1, n + 1) if mask >> (v - 1) & 1]
result.append(combo)
return result
Complexity: O(2^n · n) time, O(1) extra space. At n = 20 that is 2^20 ≈ 10^6 masks, feasible but wasteful: it examines every subset even though only C(n,k) qualify. When k is small (k = 2 yields 190 answers out of ~10^6 subsets) over 99.9% of the work is discarded.
Approach 2 — Backtracking with a start value
Generate each combination only in its canonical increasing form. The recursion carries start, the smallest value still allowed, and appends one value per level; after choosing v it recurses with v + 1, so nothing is revisited and no duplicates arise. This is the standard backtracking template: choose, recurse, un-choose.
from typing import List
def combine(n: int, k: int) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int) -> None:
if len(path) == k:
result.append(path.copy())
return
for v in range(start, n + 1):
path.append(v)
backtrack(v + 1)
path.pop()
backtrack(1)
return result
Walkthrough on n = 4, k = 2:
[1] → children [1,2], [1,3], [1,4] — three records.[2] → [2,3], [2,4].[3] → [3,4].[4] → loop over range(5, 5) is empty; the path [4] dies without a record — wasted descent.
Result: all 6 pairs, each exactly once. The recursion tree shows the slot-filling shape and the wasted [4] branch:
flowchart TD
R["path=[] start=1"]
R --> A1["[1]"]
R --> A2["[2]"]
R --> A3["[3]"]
R --> A4["[4] dead end"]
A1 --> B12["[1,2]"]
A1 --> B13["[1,3]"]
A1 --> B14["[1,4]"]
A2 --> B23["[2,3]"]
A2 --> B24["[2,4]"]
A3 --> B34["[3,4]"]
Complexity: O(C(n,k) · k) for the answers plus some dead descents like [4] above; O(k) recursion/path space.
Approach 3 — Add the counting prune
A partial path needs m = k - len(path) more values, all drawn from start..n, so it can only succeed if at least m values remain: n - start + 1 >= m, i.e. start <= n - m + 1. Encoding that in the loop bound removes every dead descent; the [4] branch in the walkthrough above is never entered.
from typing import List
def combine(n: int, k: int) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int) -> None:
if len(path) == k:
result.append(path.copy())
return
need = k - len(path)
last_useful = n - need + 1 # largest start that can still finish
for v in range(start, last_useful + 1):
path.append(v)
backtrack(v + 1)
path.pop()
backtrack(1)
return result
Walkthrough on n = 4, k = 2: at the root need = 2, so last_useful = 3 and the loop tries only 1, 2, 3 — the doomed [4] branch is pruned before it starts. One level down need = 1, last_useful = 4, and every leaf visited is a real answer.
Complexity: O(C(n,k) · k) time — now essentially all visited nodes lie on a path to an emitted answer — and O(k) space.
Approach 4 — Include/exclude binary recursion
Instead of asking “which value fills the next slot,” decide per value: value v is either in or out. This mirrors the identity C(n,k) = C(n−1,k−1) + C(n−1,k) and is the same decision shape used for Subsets. Many problems fit one framing more naturally than the other, so both are worth knowing.
from typing import List
def combine(n: int, k: int) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
def decide(v: int) -> None:
if len(path) == k:
result.append(path.copy())
return
if v > n or len(path) + (n - v + 1) < k:
return # not enough values left to reach k
path.append(v) # include v
decide(v + 1)
path.pop()
decide(v + 1) # exclude v
decide(1)
return result
Walkthrough on n = 4, k = 2: include 1 → include 2 → [1,2] recorded; exclude 2 → include 3 → [1,3]; … exclude 1 → include 2 → include 3 → [2,3]; … finally exclude 1,2 → [3,4]. Same 6 answers, generated as a binary tree of in/out decisions instead of an n-ary tree of slot fillings.
Complexity: O(C(n,k) · k) time with the feasibility check, O(n) recursion depth (one level per value rather than per slot).
Common pitfalls
- Appending
path instead of path.copy() at the leaf — all recorded answers later mutate to empty.
- Recursing with
start + 1 instead of v + 1 in the loop version — generates duplicates and permutation variants.
- Getting the prune bound wrong (
n - need vs n - need + 1) — test it on k = n, where the loop must still allow exactly one chain.
- In the include/exclude version, forgetting the
len(path) == k check before the exhaustion check — k = n answers arrive exactly when v = n + 1.
Pattern takeaway
Combinations is the skeleton under Combination Sum, Subsets, and related problems: a start parameter makes increasing order the canonical form (no duplicates by construction), and a counting prune — do enough choices remain to fill the remaining slots? — trims every hopeless branch at O(1) cost. Keep both framings available: slot-centric loops (which value goes next?) and value-centric binary decisions (is this value in?) generate the same set, and harder problems often yield to one framing more cleanly than the other.