BacktrackingRecursion & Backtracking

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.

Learn Combinations (n choose k) →

n | k — Choose k numbers from 1..n — e.g. "4 | 2". n ≤ 5

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

Complexity

worst O(k · C(n, k))

space O(k)

Speed