BacktrackingAlgorithmaka k-subsets, n choose k, combination sum

Combinations (n choose k)

Enumerate all size-k subsets of n elements using the start-index template with a size-based base case and a "not enough elements left" prune.

▶ VisualizePattern: BacktrackingPractice (2)
Progress

Overview

A combination is an unordered selection of exactly k items from n; there are C(n, k) = n! / (k!(n−k)!) of them. The algorithm is the Subsets (Power Set) start-index template with two changes: record only when len(path) == k, and prune when the remaining elements cannot fill the path (n − i < k − len(path)).

Combination Sum generalizes the base case from "size equals k" to "sum equals target" and, when reuse is allowed, recurses with i instead of i + 1.

backtrackingC(n,k)start indexpruningcombination sum

Intuition

A mental model before the formal terms.

Choosing 3 people from a line of 7: point at someone, then only consider people to their right for the next pick. That rule alone stops you from picking the same trio in a different order.

The prune is counting how many people remain to your right: if you still need 2 more picks and only 1 person is left, stop looking down this branch.

How it works

  1. Call backtrack(start=0, path=[]).
  2. If len(path) == k, record a copy and return.
  3. Loop i from start while n − i ≥ k − len(path) (enough elements remain): push a[i], recurse with i + 1, pop.
  4. For combination sum with reuse: base case remaining == 0; prune when a[i] > remaining after sorting; recurse with i (not i + 1).

Why it works

Each k-combination corresponds to exactly one increasing index sequence of length k, which the start-index loop enumerates once.

The remaining-count prune is exact: once fewer than k − len(path) elements remain, no completion exists, so skipping is safe and cuts the tree from O(2^n) nodes to roughly O(C(n,k) · k).

Recognition

How to tell a problem wants this.

  • "Choose exactly k", "all combinations that sum to target", "select a group of size k".
  • Order of chosen items is explicitly irrelevant — output [1,2] but not [2,1].
  • Small n (≤ 20) and an output list of combinations is expected.
“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

Call stack (top first)
empty
Combinations (0)
empty
1/27Choose 2 of {1..4}: pick numbers in increasing order so each combination is generated exactly once.
Call on the stackCall returnedJust placed
PseudocodeLearn Combinations (n choose k) →
1go(start, current):
2  if len(current) == k: record(current); return
3  for x in start .. n:
4    if n - x + 1 < k - len(current): break   // prune: not enough left
5    current.push(x); go(x + 1, current)
6    current.pop()                             // backtrack
Variables
n4
k2
Complexity
worst O(k · C(n, k))
space O(k)
Speed

Pseudocode

1backtrack(start, path):
2  if len(path) == k: record(copy of path); return
3  for i in start..n-1:
4    if n - i < k - len(path): break   # not enough left
5    path.push(a[i])
6    backtrack(i + 1, path)
7    path.pop()
8backtrack(0, [])

Implementations

1def combinations(n: int, k: int) -> list[list[int]]:
2    """All k-combinations of 1..n."""
3    out: list[list[int]] = []
4    path: list[int] = []
5 
6    def backtrack(start: int) -> None:
71 · Base case: k chosen
8        if len(path) == k:
9            out.append(path[:])
10            return
112 · Prune the loop bound
12        need = k - len(path)
13        for i in range(start, n - need + 2):   # leave enough elements
143 · Choose / explore / un-choose
15            path.append(i)
16            backtrack(i + 1)
17            path.pop()
18 
19    backtrack(1)
20    return out
21 
22 
234 · Combination sum with unlimited reuse
24def combination_sum(cands: list[int], target: int) -> list[list[int]]:
25    cands = sorted(cands)
26    out: list[list[int]] = []
27    path: list[int] = []
28 
29    def backtrack(start: int, remaining: int) -> None:
30        if remaining == 0:
31            out.append(path[:])
32            return
33        for i in range(start, len(cands)):
34            if cands[i] > remaining:
35                break            # sorted: nothing later fits
36            path.append(cands[i])
37            backtrack(i, remaining - cands[i])   # i, not i + 1: reuse allowed
38            path.pop()
39 
40    backtrack(0, target)
41    return out
Walkthrough
  1. range(start, n - need + 2) is the prune: the upper bound is exclusive, hence + 2 instead of the + 1 used in the other languages.
  2. out.append(path[:]) stores a copy once k elements are chosen.
  3. backtrack(i + 1) in combinations forbids reuse; backtrack(i, ...) in combination_sum allows it.
  4. break on cands[i] > remaining is valid only because cands is sorted.
Complexity (this implementation)
time O(k * C(n, k)) for combinations; exponential for combination_sum · space O(k) recursion depth plus output
Language notes
  • itertools.combinations(range(1, n + 1), k) produces the same output lazily in C; itertools.combinations_with_replacement covers multisets.
  • range upper bounds are exclusive, which is where the + 2 comes from.
  • Depth is at most k (or target / min candidate), far below the recursion limit.
Common mistakes in this language
  • Off-by-one in the range bound after translating <= n - need + 1 from another language.
  • Appending path instead of path[:].
  • Using continue instead of break in the sorted prune, which is correct but wastes the pruning benefit.
Language differences that matter here
  • Python's range has an exclusive upper bound, so the prune reads n - need + 2 versus i <= n - need + 1 in C++/JS/TS.
  • Only Python has a built-in combinations generator (itertools); C++ can emulate with prev_permutation over a selector mask; JS/TS hand-roll it.
  • JS/TS require sort((a, b) => a - b) before the sorted-prune break is valid.

Complexity

Best
—
Average
—
Worst
O(k · C(n, k))
Space
O(k)

With the remaining-count prune every internal node leads to at least one leaf, so work is proportional to output size. Combination sum is exponential in target / min(candidate).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Enumerate all fixed-size selections, or all multisets summing to a target, for small inputs.
  • Search over selections where a cheap prefix test (sum, size, remaining budget) prunes most branches.
Avoid it when

Alternatives

Subsets (Power Set)CombinatoricsCoin ChangeUnbounded Knapsack

Common mistakes

  • Off-by-one in the prune bound i <= n - need + 1 (1-indexed) — test with k == n.
  • In combination sum, recursing with i + 1 when reuse is allowed (misses [2,2,3]) or with i when it is not (produces repeats).
  • Forgetting to sort before break-ing on c[i] > remaining; with unsorted input use continue instead.
  • Combination Sum II (each element once, duplicates in input) needs the Subsets (Power Set) duplicate skip i > start && c[i] == c[i-1].

Interview patterns

  • Combination Sum I / II / III: vary reuse, duplicate handling, and size constraint.
  • Factor combinations, palindrome partitioning: the "element" is a chunk of the input, chosen from a start index.
  • Phone-keypad letter combinations: cross product of per-position choice sets, no start index needed.
Interview questions on this
Mock interviews

Example problems

SubsetsmediumCombination Summedium