AlgoVerse

Generating all combinations

Build all k-element subsets of 1 to n in lexicographic order; each next item is larger than the last, so no subset comes twice.

So that no subset comes twice (in different orders), the items are kept increasing: after x, only items larger than x are tried.

Read the full explanation ↓
Input:
n=5 · k=3PDF export

The 3-element subsets of 5 items: C(5, 3) = 10 combinations, from 123 to 345.

  1. def combinations(n, k):
  2. current = []
  3. rows = []
  4. extend(1, n, k, current, rows)
  5. return len(rows)
  8. def extend(start, n, k, current, rows):
  9. if len(current) == k:
  10. rows.append(tuple(current))
  11. return
  12. # Leave room for the items still needed: the last start that can still complete a combination.
  13. last = n - (k - len(current)) + 1
  14. for x in range(start, last + 1):
  15. current.append(x)
  16. extend(x + 1, n, k, current, rows)
  17. current.pop()

Invariant: current is always increasing and still leaves room for the items it needs.

Start

current—

The table is still empty.

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

n5
k3

Orange = changed in this step

Call stack

  1. combinations()line 1
Step 1 of 161
Black = found · Orange = key stepchoose: 0/19 · found: 0/10 · undo: 0/19
    Explanation

    The idea

    So that no subset comes twice (in different orders), the items are kept increasing: after x, only items larger than x are tried.

    Pruning

    If r more items are needed, starting above n − r + 1 is pointless, because not enough items would be left. With this bound, every branch that opens reaches at least one combination.

    Cost

    C(n, k) = n! / (k! (n − k)!) combinations of k items each.

    What to watch in the trace

    • Compare the call tree with the "generating all permutations" page: here each level only tries larger numbers.