vault

Combinations

14 min read

Combinations

A combination is an unordered selection of k elements from a set of n. The set {1, 2, 3} has C(3, 2) = 3 combinations of size 2: {1,2}, {1,3}, {2,3} — note that {2, 1} is the same combination as {1, 2} because order doesn’t matter. The interview canon contains four combination problems: (1) enumerate all C(n, k) k-subsets of {1, ..., n} (LeetCode 77); (2) enumerate all combinations summing to a target with each element usable infinitely (LeetCode 39 Combination Sum); (3) the same with each element usable at most once and a sorted input that may contain duplicates (LeetCode 40 Combination Sum II); and (4) k-combinations of a sorted input with duplicates treated as a set, which uses the same sort-plus-level-skip technique that recurs across Permutations and Subsets. The clean implementation pattern in every case is backtracking with a start index that enforces an increasing-position ordering — this single discipline is what suppresses the order-as-different-combination duplication that would otherwise multiply each combination by k! permutations of itself.

1. Intuition — Pick or Skip, Left to Right

To list every 2-element subset of {1, 2, 3, 4}:

  • For each position in the output, the rule is “the next chosen element must come after the previous one in the input order.”
  • Start at the leftmost slot. Choices are 1, 2, 3 — but not 4 (you’d never have room for a second element after).
  • Whatever you chose, the next slot’s choices begin one position after what you just chose.

This increasing-position invariant is what kills the k!-fold redundancy: by always picking elements left-to-right in the original input, you visit each subset exactly once (in the order {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} for n=4, k=2). Without it you’d visit {1,2} and {2,1} and have to deduplicate.

The start index in the canonical implementation is exactly this rule: at recursion depth d, only positions start, start+1, ..., n-1 are eligible — never positions < start. After picking position i, the recursive call uses start = i + 1.

2. Tiny Worked Example — All C(4, 2) = 6 Combinations

State-space tree of the canonical backtracker (n = 4, k = 2):

               []  start=0
        ┌───────┼───────┬───────┐
       [1]     [2]     [3]    (skip [4]: no room for 2nd pick)
       /│\     /│\      │
   [1,2][1,3][1,4]  [2,3][2,4]   [3,4]    ← 6 leaves

The 6 leaves are exactly the 6 combinations of {1,2,3,4} choose 2. The “skip [4]” prune is one form of optimisation discussed in §6 (early abort when not enough remaining elements).

The trace, walked left-to-right with path and the recursion’s start parameter:

Recursion callpath on entryIterates i overLeaf emitted?
go(start=0)[]0, 1, 2, (3 abortable)no
↳ go(start=1) (after picking 1)[1]1, 2, 3leaves at i = 1, 2, 3
↳ go(start=2) (after picking 2)[2]2, 3leaves at i = 2, 3
↳ go(start=3) (after picking 3)[3]3leaf at i = 3

Total: 6 leaves. The number of internal nodes is small because k = 2 is shallow.

3. Pseudocode — The Backtracking Schema

combine(n, k):
    results := []
    path := []

    define go(start):
        if length(path) == k:
            append copy(path) to results
            return
        for i := start to n - 1:
            push (i + 1) onto path     # values are 1-indexed in LC 77
            go(i + 1)
            pop path

    go(0)
    return results

The five Backtracking Framework primitives:

  • is_solution(state) ↔ length(path) == k
  • choices(state) ↔ iterate i from start to n - 1
  • valid(choice, state) ↔ implicit (any i ≥ start is admissible)
  • apply(choice, state) ↔ push (i+1) (using 1-indexed values for LC 77)
  • undo(choice, state) ↔ pop
  • The new ingredient: the start parameter, which encodes “the next pick must come after start”. It is not part of path itself; it lives in the recursion’s argument list.

4. Python Implementations

4.1 Combinations of {1..n} Choose k (LeetCode 77)

def combine(n: int, k: int) -> list[list[int]]:
    results: list[list[int]] = []
    path: list[int] = []
 
    def go(start: int):
        if len(path) == k:
            results.append(path[:])
            return
        for i in range(start, n):
            path.append(i + 1)         # 1-indexed values
            go(i + 1)
            path.pop()
 
    go(0)
    return results

For n = 4, k = 2 this returns [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] — exactly the 6 combinations from §2.

4.2 With Pruning (Early Abort When Not Enough Remaining)

A frequently-asked optimisation: if there are fewer remaining elements than slots still to fill, abort the loop. This converts a polynomial-by-polynomial search into a much tighter walk.

def combine_pruned(n: int, k: int) -> list[list[int]]:
    results, path = [], []
 
    def go(start: int):
        if len(path) == k:
            results.append(path[:])
            return
        # Need (k - len(path)) more elements; can't take i if there aren't enough left.
        # Largest i we can take and still fit (k - len(path)) elements = n - (k - len(path))
        max_i = n - (k - len(path))
        for i in range(start, max_i + 1):
            path.append(i + 1)
            go(i + 1)
            path.pop()
 
    go(0)
    return results

The pruning is max_i = n - (k - len(path)) instead of the raw n - 1. For n = 100, k = 5, the unpruned loop wastes a lot of time exploring path = [1] followed by i = 99 (no room for 4 more). The prune kills those upfront.

4.3 Combination Sum (LeetCode 39) — Repeats Allowed

Given an array of distinct positive integers candidates and a target, find all combinations summing to target where each candidate may be used unlimited times. The trick: when recursing after picking candidates[i], the next call uses start = i (not i + 1) — allowing the same index to be reused, while still enforcing increasing-or-equal index order to suppress permutational duplicates.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    candidates = sorted(candidates)        # sort to allow early prune
    results, path = [], []
 
    def go(start: int, remaining: int):
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:  # sorted, so all later are too big
                break
            path.append(candidates[i])
            go(i, remaining - candidates[i])    # i, not i+1: reuse allowed
            path.pop()
 
    go(0, target)
    return results

The start = i in the recursive call is what allows reuse. The if candidates[i] > remaining: break is the bound prune — sorted input means once candidates[i] exceeds remaining, every later candidates[j] does too.

4.4 Combination Sum II (LeetCode 40) — Each Element Once, Duplicates in Input

Now candidates may have repeated values, each may be used at most once, and we want each distinct combination once. Sort + level-skip:

def combination_sum_2(candidates: list[int], target: int) -> list[list[int]]:
    candidates = sorted(candidates)
    results, path = [], []
 
    def go(start: int, remaining: int):
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            # Skip duplicate at the same recursion level
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            go(i + 1, remaining - candidates[i])    # i+1: each used once
            path.pop()
 
    go(0, target)
    return results

The duplicate-skip predicate if i > start and candidates[i] == candidates[i - 1]: continue is the canonical pattern for “sort + dedupe at the same level”. Why does it work?

Imagine candidates = [1, 1, 2] and we are at the recursion-tree root (start = 0). The loop iterates i = 0, 1, 2:

  • i = 0: candidates[0] = 1. We pick it. Recurse with start = 1.
  • i = 1: candidates[1] = 1, equals candidates[0], and i > start = 0 → skip.
  • i = 2: candidates[2] = 2. Pick.

The skip prevents starting a second root-to-… path with 1 (which would produce the same combinations as the first 1 did). However, inside the first 1’s subtree, the recursion enters with start = 1. Now if we are looking at candidates[1] = 1, the predicate i > start is 1 > 1 = False, so we don’t skip. This is correct: within the path that already includes the first 1, picking the second 1 extends to [1, 1, ...], which is a legitimately different combination from [1, ...] alone.

The condition i > start (not i > 0) is the subtle part. i > 0 would erroneously skip the first instance of a duplicate even inside a recursion call where it’s the leftmost choice in that subtree. i > start correctly skips only when the duplicate is encountered as a sibling of an earlier-in-the-loop equal value.

4.5 Lexicographic Order vs Combinatorial Number System

The backtracker emits combinations in lexicographic order on the input ordering: for sorted nums, the output is sorted by first element, then second, etc. This matches LC’s expected output for combination problems.

A different ordering, the combinatorial number system (Wikipedia; Knuth TAOCP 4A §7.2.1.3), gives a one-to-one bijection between integers in [0, C(n, k)) and k-combinations of {0, ..., n-1}. Useful when you want to index into the set of combinations directly without enumerating predecessors. This rarely appears in interviews.

A third ordering — Gray code for combinations (revolving-door algorithm; Knuth 4A §7.2.1.3) — generates combinations such that consecutive combinations differ by exactly one swap (one element out, one in). Analogous to the binary Gray code for Subsets. Useful for hardware-state minimisation and for problems where re-evaluating a property is cheap given a single change.

5. Complexity

5.1 Counting Operations

The recursion visits exactly C(n, k) leaves. Each leaf snapshot is O(k) work. Total time: O(k · C(n, k)).

The number of internal recursion nodes is bounded by Σ_{j=0..k} C(n, j) ≤ k · C(n, k) — the same order. So total time including internal work is O(k · C(n, k)).

nkC(n, k)k · C(n, k)
103120360
20101847561.85 × 10⁶
30151551175202.33 × 10⁹

The middle column hits ~1.85 × 10⁶ at n = 20, k = 10 — feasible. At n = 30, k = 15 we’re at 2.3 × 10⁹ — infeasible without further pruning or a different formulation.

5.2 Space

Recursion stack depth is k. The shared path is length at most k. Auxiliary memory excluding output: O(k). Output memory: O(k · C(n, k)).

5.3 The Bound Σ C(n, j) = 2^n

An aside that’s surprisingly relevant: the total number of subsets across all k from 0 to n is 2^n. So enumerating combinations of all sizes (LC 78 Subsets) takes O(n · 2^n) time. This is the bridge between Subsets and Combinations — subsets is the union over k = 0..n of combinations.

6. Pruning Strategies

6.1 Early Abort on Insufficient Remaining (§4.2)

max_i = n - (k - len(path)). If you’d need m more elements but fewer than m are left, abort.

6.2 Sorted Input + Bound on Sum (§4.3, §4.4)

For combination-sum problems, sorting the candidates allows if candidates[i] > remaining: break to short-circuit the inner loop. Without sorting you’d have to use continue instead and waste iterations.

6.3 Duplicate Skip at Same Level (§4.4)

if i > start and candidates[i] == candidates[i - 1]: continue. The single most error-prone line in combinatorial backtracking. Worth memorising. (See Subsets §X for the same predicate applied to subsets, and Permutations §4.4 for the closely related but slightly different predicate using used[i-1].)

6.4 Memoization

For counting combinations (rather than enumerating them), use Pascal’s triangle: C(n, k) = C(n-1, k-1) + C(n-1, k), computed in O(n · k) with a 2D DP table. This is what Memoization vs Tabulation would do for the count; the enumeration version cannot be memoized because each path produces a different output.

7. Diagram — State-Space Tree for n = 4, k = 2

flowchart TD
    R["[]<br/>start=0"]
    R --> A1["[1]<br/>start=1"]
    R --> A2["[2]<br/>start=2"]
    R --> A3["[3]<br/>start=3"]
    R -. pruned .-> X["[4]<br/>(no room for 2nd pick)"]
    A1 --> L12["[1,2]"]
    A1 --> L13["[1,3]"]
    A1 --> L14["[1,4]"]
    A2 --> L23["[2,3]"]
    A2 --> L24["[2,4]"]
    A3 --> L34["[3,4]"]

    style X stroke-dasharray: 5 5,stroke:#a33

What this diagram shows. Each node is a partial combination; the start parameter on each node is the minimum next index allowed. The start increases monotonically as we descend, which is what enforces increasing-position ordering and prevents permutational duplicates. The dashed [4] node is what the §4.2 pruning eliminates: with only k − 1 = 1 slot left and 0 elements remaining after position 4, the subtree contains no leaves so we don’t bother entering. Solid leaves are the 6 combinations.

8. Pitfalls

  1. Using i + 1 vs i in the recursive call. With repeats forbidden, recurse with start = i + 1 (each element used at most once). With repeats allowed (LC 39), recurse with start = i. Mixing them up is silent: you’ll either produce too many results (used i when you meant i + 1) or miss valid ones (vice versa).
  2. Wrong duplicate-skip predicate. if i > start and ..., not if i > 0 and .... The latter erroneously skips legitimate first-of-a-duplicate-group choices inside subtrees. (See §4.4.)
  3. Forgetting to sort before deduplication. The level-skip relies on equal values being adjacent. [2, 1, 2] without sorting won’t deduplicate; sort it to [1, 2, 2] first.
  4. Order of duplicate-skip and bound-skip. When you have both if duplicate: continue and if too_big: break, put continue first and break second, but check carefully — for some problems the duplicate skip should come after the bound. The standard idiom is dup-check → bound-check → apply → recurse → undo and that order works in all the problems referenced here.
  5. Not snapshotting at the leaf. results.append(path) aliases the same list. (Same trap as Permutations §9.1 and Subsets §9.1.)
  6. Confusing combinations with permutations. [1, 2] and [2, 1] are the same combination but different permutations. If the problem says “all subsets of size k”, that’s combinations. “All k-tuples” is permutations.
  7. Off-by-one in 1-indexing for LC 77. The problem statement uses values {1, ..., n} but Python loops are 0-indexed. The fix is to either iterate i over range(n) and emit i + 1, or iterate over range(1, n + 1) directly. Mixing the two produces empty results or out-of-bounds.
  8. Treating start as part of path. The start parameter is recursion bookkeeping and must not be appended into the result. It’s a separate argument.
  9. Iterating with the wrong loop bounds when pruning. The pruned loop is for i in range(start, max_i + 1) (note the + 1 because range is exclusive). Off-by-one here silently misses combinations.
  10. Using a set to deduplicate after the fact. Yes, that works for small n, but it converts an O(k · C(n, k)) algorithm into something with hashing overhead and garbage allocations. The level-skip is in-place and O(1) per skip — strictly better.
  11. Generating combinations by generating permutations and deduplicating. A common interview anti-pattern: set(map(tuple, sorted(p) for p in permutations(arr, k))). This is O(k · n!) instead of O(k · C(n, k)) — exponentially worse.
  12. Mutable default argument def go(path=[]): .... Same Python gotcha as Permutations §9.8.

9. Common Interview Problems

ProblemLeetCodeDifficultyVariation
Combinations77Mediumk-subsets of {1..n}
Combination Sum39MediumRepeats allowed; sum to target
Combination Sum II40MediumNo repeats; duplicates in input → sort + level-skip
Combination Sum III216Mediumk-subsets of {1..9} summing to target
Letter Combinations of Phone Number17MediumCartesian product (sometimes classified as combinations)
Combinations of Phone Letters / Word Patterns89 (Gray Code)MediumBit-pattern enumeration; see Gray code
Generate Parentheses22MediumCombinations with structural constraints — see Generate Parentheses

10. Open Questions

  • When does the combinatorial number system beat enumeration? Roughly: when you need random access to the i-th combination (e.g., an O(k log n) lookup) without computing the others. Rare in interviews; common in cryptography ranking algorithms.
  • Knuth 4A §7.2.1.3 lists ~5 different orderings for combinations (lex, co-lex, revolving-door, banker’s, etc.). Are any other than lex and Gray-code-style asked in interviews? Probably not.
  • How does the algorithm change when k itself is the variable being enumerated (LC 78 Subsets)? Drops the is_solution check; record at every node, not just leaves of depth k.

11. See Also

Graph View

Backlinks