Combinations

Choose k elements out of n where order doesn't matter. Nearly identical to Subsets, but each recursive call only considers indices at or after the current one — that's what prevents generating both {A,B} and {B,A}.

Category

Backtracking

Time complexity

O(C(n,k))

Space complexity

O(k)

Pseudocode

combine(start, path):
  if len(path) == k: emit path
  for i in start..n-1:
    path.push(a[i]); combine(i+1, path); path.pop()

Reference implementation

def combine(start, path, n, k, out):
    if len(path) == k:
        out.append(list(path)); return
    for i in range(start, n):
        path.append(i)
        combine(i + 1, path, n, k, out)
        path.pop()

Open the interactive Combinations visualisation →