AlgoScope

Enumeration

Generating every subset or every ordering is a tree of choices walked depth-first. Subsets: at each element, include it and recurse, then undo and exclude it and recurse. Permutations: for each position, swap each remaining element in, recurse, and swap it back. Every leaf is one answer, and the undo after each branch is what lets the same array serve every path. Meet in the middle is the trick for when 2 to the n is too many but 2 to the n over 2 is fine: split the input in half, enumerate each half on its own, sort one side, and look up each sum from the other side in it. Two lists of the square root of the size replace one enormous one.

The player

Generating all 8 subsets of 3 values by include-or-exclude recursion.102132

Every subset of {1, 2, 3}. Look at one element at a time: include it and go on, then come back, exclude it and go on. Reaching the end of the array is a leaf, and every leaf is a different subset: 2 to the 3 = 8 of them.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.

  1. Including 1 leaves 2 elements to decide. How many subsets come out of this branch?

    • 3
    • 4
    • 8

    Answer: 4. Each remaining element doubles the count: 2 to the 2 = 4. The exclude branch will produce the same number again.

  2. Including 2 leaves 1 element to decide. How many subsets come out of this branch?

    • 2
    • 4

    Answer: 2. Each remaining element doubles the count: 2 to the 1 = 2. The exclude branch will produce the same number again.

  3. Including 3 leaves 0 elements to decide. How many subsets come out of this branch?

    • 1
    • 2

    Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.

  4. Including 3 leaves 0 elements to decide. How many subsets come out of this branch?

    • 1
    • 2

    Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.

  5. Including 2 leaves 1 element to decide. How many subsets come out of this branch?

    • 2
    • 4

    Answer: 2. Each remaining element doubles the count: 2 to the 1 = 2. The exclude branch will produce the same number again.

  6. Including 3 leaves 0 elements to decide. How many subsets come out of this branch?

    • 1
    • 2

    Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.

  7. Including 3 leaves 0 elements to decide. How many subsets come out of this branch?

    • 1
    • 2

    Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.

How it runs, step by step

  1. Every subset of {1, 2, 3}. Look at one element at a time: include it and go on, then come back, exclude it and go on. Reaching the end of the array is a leaf, and every leaf is a different subset: 2 to the 3 = 8 of them.

    Generating all 8 subsets of 3 values by include-or-exclude recursion.

  2. Element 0 is 1. First branch: include it, chosen is now {1}. Go deeper.

    Include 1 and recurse.

  3. Element 1 is 2. First branch: include it, chosen is now {1, 2}. Go deeper.

    Include 2 and recurse.

  4. Element 2 is 3. First branch: include it, chosen is now {1, 2, 3}. Go deeper.

    Include 3 and recurse.

  5. Past the last element: a leaf. Subset 1: {1, 2, 3}.

    Leaf. Subset 1 is {1, 2, 3}.

  6. Back at element 2. Undo: drop 3, chosen is {1, 2}. Second branch: exclude it and go deeper.

    Exclude 3 and recurse.

  7. Past the last element: a leaf. Subset 2: {1, 2}.

    Leaf. Subset 2 is {1, 2}.

  8. Back at element 1. Undo: drop 2, chosen is {1}. Second branch: exclude it and go deeper.

    Exclude 2 and recurse.

  9. Element 2 is 3. First branch: include it, chosen is now {1, 3}. Go deeper.

    Include 3 and recurse.

  10. Past the last element: a leaf. Subset 3: {1, 3}.

    Leaf. Subset 3 is {1, 3}.

  11. Back at element 2. Undo: drop 3, chosen is {1}. Second branch: exclude it and go deeper.

    Exclude 3 and recurse.

  12. Past the last element: a leaf. Subset 4: {1}.

    Leaf. Subset 4 is {1}.

  13. Back at element 0. Undo: drop 1, chosen is { }. Second branch: exclude it and go deeper.

    Exclude 1 and recurse.

  14. Element 1 is 2. First branch: include it, chosen is now {2}. Go deeper.

    Include 2 and recurse.

  15. Element 2 is 3. First branch: include it, chosen is now {2, 3}. Go deeper.

    Include 3 and recurse.

  16. Past the last element: a leaf. Subset 5: {2, 3}.

    Leaf. Subset 5 is {2, 3}.

  17. Back at element 2. Undo: drop 3, chosen is {2}. Second branch: exclude it and go deeper.

    Exclude 3 and recurse.

  18. Past the last element: a leaf. Subset 6: {2}.

    Leaf. Subset 6 is {2}.

  19. Back at element 1. Undo: drop 2, chosen is { }. Second branch: exclude it and go deeper.

    Exclude 2 and recurse.

  20. Element 2 is 3. First branch: include it, chosen is now {3}. Go deeper.

    Include 3 and recurse.

  21. Past the last element: a leaf. Subset 7: {3}.

    Leaf. Subset 7 is {3}.

  22. Back at element 2. Undo: drop 3, chosen is { }. Second branch: exclude it and go deeper.

    Exclude 3 and recurse.

  23. Past the last element: a leaf. Subset 8: { }.

    Leaf. Subset 8 is { }.

  24. 8 subsets: {1, 2, 3} {1, 2} {1, 3} {1} {2, 3} {2} {3} { }. Every element was included once and excluded once at each point in the tree, so the leaves number 2 to the 3 and none repeats.

    8 subsets were generated.

The code

Enumeration, in Python

def subsets(a, i=0, chosen=None):
    if chosen is None: chosen = []                  # a fresh list per top-level call
    if i == len(a): emit(chosen); return            # a leaf: one subset
    chosen.append(a[i])                             # include a[i]
    subsets(a, i + 1, chosen)
    chosen.pop()                                    # undo
    subsets(a, i + 1, chosen)                       # exclude a[i]

def permutations(a, i=0):
    if i == len(a): emit(a); return                 # a leaf: one ordering
    for k in range(i, len(a)):
        a[i], a[k] = a[k], a[i]                     # put a[k] in position i
        permutations(a, i + 1)
        a[i], a[k] = a[k], a[i]                     # undo, so the next k starts clean

def combinations(a, k, start=0, chosen=None):
    if chosen is None: chosen = []                  # a fresh list per top-level call
    if len(chosen) == k: emit(chosen); return       # a leaf: one combination
    for i in range(start, len(a)):                  # only later indices: no repeats, no reorderings
        chosen.append(a[i])
        combinations(a, k, i + 1, chosen)
        chosen.pop()                                # undo

def combination_sum(a, target, start=0, chosen=None):
    if chosen is None: chosen = []                  # a fresh list per top-level call
    if target == 0: emit(chosen); return            # the picks add up exactly
    for i in range(start, len(a)):                  # start at i again: a candidate may repeat
        if a[i] > target: continue                  # prune: this pick alone overshoots
        chosen.append(a[i])
        combination_sum(a, target - a[i], i, chosen)
        chosen.pop()                                # undo

def meet_in_the_middle(a, target):
    left = a[:len(a) // 2]; right = a[len(a) // 2:]
    left_sums = subset_sums(left)                   # 2^(n/2) sums instead of 2^n subsets
    right_sums = sorted(subset_sums(right))         # sorted once, so each lookup is a binary search
    for s in left_sums:
        j = bisect_left(right_sums, target - s)
        if j < len(right_sums) and right_sums[j] == target - s: return True   # the halves meet
    return False
def subset_sums(a): return [sum(a[i] for i in range(len(a)) if m >> i & 1 == 1) for m in range(1 << len(a))]

Enumeration, in JavaScript

function subsets(a, i = 0, chosen = []) {
  if (i === a.length) { emit(chosen); return; }         // a leaf: one subset
  chosen.push(a[i]);                                    // include a[i]
  subsets(a, i + 1, chosen);
  chosen.pop();                                         // undo
  subsets(a, i + 1, chosen);                            // exclude a[i]
}

function permutations(a, i = 0) {
  if (i === a.length) { emit(a); return; }              // a leaf: one ordering
  for (let k = i; k < a.length; k++) {
    [a[i], a[k]] = [a[k], a[i]];                        // put a[k] in position i
    permutations(a, i + 1);
    [a[i], a[k]] = [a[k], a[i]];                        // undo, so the next k starts clean
  }
}

function combinations(a, k, start = 0, chosen = []) {
  if (chosen.length === k) { emit(chosen); return; }    // a leaf: one combination
  for (let i = start; i < a.length; i++) {              // only later indices: no repeats, no reorderings
    chosen.push(a[i]);
    combinations(a, k, i + 1, chosen);
    chosen.pop();                                       // undo
  }
}

function combinationSum(a, target, start = 0, chosen = []) {
  if (target === 0) { emit(chosen); return; }           // the picks add up exactly
  for (let i = start; i < a.length; i++) {              // start at i again: a candidate may repeat
    if (a[i] > target) continue;                        // prune: this pick alone overshoots
    chosen.push(a[i]);
    combinationSum(a, target - a[i], i, chosen);
    chosen.pop();                                       // undo
  }
}

function meetInTheMiddle(a, target) {
  const half = Math.floor(a.length / 2);
  const left = a.slice(0, half); const right = a.slice(half);
  const leftSums = subsetSums(left);                    // 2^(n/2) sums instead of 2^n subsets
  const rightSums = subsetSums(right).sort((x, y) => x - y);   // sorted once, so each lookup is a binary search
  const has = (v) => {                                  // no stdlib binary search in JS, so here it is
    let lo = 0, hi = rightSums.length - 1;
    while (lo <= hi) {
      const m = (lo + hi) >> 1;
      if (rightSums[m] === v) return true;
      if (rightSums[m] < v) lo = m + 1; else hi = m - 1;
    }
    return false;
  };
  for (const s of leftSums) if (has(target - s)) return true;   // the halves meet
  return false;
}
function subsetSums(a) { return Array.from({ length: 1 << a.length }, (_, m) => a.reduce((sum, v, i) => ((m >> i) & 1) === 1 ? sum + v : sum, 0)); }

Enumeration, in Kotlin

fun subsets(a: IntArray, i: Int = 0, chosen: MutableList<Int> = mutableListOf()) {
    if (i == a.size) { emit(chosen); return }          // a leaf: one subset
    chosen += a[i]                                      // include a[i]
    subsets(a, i + 1, chosen)
    chosen.removeLast()                                 // undo
    subsets(a, i + 1, chosen)                           // exclude a[i]
}

fun permutations(a: IntArray, i: Int = 0) {
    if (i == a.size) { emit(a); return }                // a leaf: one ordering
    for (k in i until a.size) {
        a.swap(i, k)                                    // put a[k] in position i
        permutations(a, i + 1)
        a.swap(i, k)                                    // undo, so the next k starts clean
    }
}

fun combinations(a: IntArray, k: Int, start: Int = 0, chosen: MutableList<Int> = mutableListOf()) {
    if (chosen.size == k) { emit(chosen); return }      // a leaf: one combination
    for (i in start until a.size) {                     // only later indices: no repeats, no reorderings
        chosen += a[i]
        combinations(a, k, i + 1, chosen)
        chosen.removeLast()                             // undo
    }
}

fun combinationSum(a: IntArray, target: Int, start: Int = 0, chosen: MutableList<Int>) {
    if (target == 0) { emit(chosen); return }          // the picks add up exactly
    for (i in start until a.size) {                     // start at i again: a candidate may repeat
        if (a[i] > target) continue                     // prune: this pick alone overshoots
        chosen += a[i]
        combinationSum(a, target - a[i], i, chosen)
        chosen.removeLast()                             // undo
    }
}

fun meetInTheMiddle(a: IntArray, target: Int): Boolean {
    val left = a.copyOfRange(0, a.size / 2); val right = a.copyOfRange(a.size / 2, a.size)
    val leftSums = subsetSums(left)                     // 2^(n/2) sums instead of 2^n subsets
    val rightSums = subsetSums(right).sorted()          // sorted once, so each lookup is a binary search
    for (s in leftSums) if (rightSums.binarySearch(target - s) >= 0) return true   // the halves meet
    return false
}
fun subsetSums(a: IntArray) = (0 until (1 shl a.size)).map { m -> a.indices.filter { m shr it and 1 == 1 }.sumOf { a[it] } }

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Subsets: include or exclude each element, 2^n leaves. Permutations: swap each candidate into each position, n! leaves.
  • Undo after every branch, or later branches start from a corrupted state.
  • These counts are the whole cost, so the technique only works for small n. Meet in the middle stretches it to about twice the n by enumerating two halves and joining them with a sorted lookup.

Where this is used

PostgreSQL choosing a join orderDatabases

The planner searches join orders by working over subsets of the tables in the query, keeping the cheapest plan found for each subset, so a five-table query plans instantly while an exhaustive search over fifteen tables would not. PostgreSQL stops searching exhaustively at geqo_threshold, twelve tables by default, and hands the problem to a genetic algorithm that samples orders instead. That threshold is the line where 2^n stops being affordable, written into a config file.

Meet in the middle against double DESSecurity

Encrypting twice under two 56-bit keys looks like 112 bits of work to break, but an attacker encrypts a known plaintext under every first key, sorts those results, then decrypts the ciphertext under every second key and looks for a hit: two enumerations of 2^56 joined by a lookup rather than one search of 2^112. Diffie and Hellman published this in 1977, and it is why DES was tripled rather than doubled. The name describes the shape shared by both: work forward from one end, backward from the other, and match where the two sides meet.

Python's itertoolsStandard libraries

itertools.combinations, permutations and product are these exact walks written as lazy generators: each call yields one tuple and keeps only the current index vector, so enumerating the orderings of ten items never holds 3.6 million tuples at once. combinations advances the rightmost index that still has room, which is the loop-with-a-start-index shape used here rather than the recursive one. The powerset recipe in the docs is just combinations run for every length.

SuperoptimizersCompilers

A superoptimizer finds the shortest instruction sequence computing a function by enumerating every sequence of length one, then two, then three, testing each against the target. Massalin's 1987 superoptimizer and the GNU superoptimizer after it found sequences that hand-written compiler rules had missed, but only very short ones, because each extra instruction multiplies the search space by the size of the instruction set. It is the cleanest example of enumeration being complete and correct and still bounded entirely by how far small n reaches.

Why it works this way

Why combinations pass i + 1 and combination sum passes i

The start index is the entire duplicate-avoiding mechanism. Passing i + 1 says every later pick must come from a later index, so {1, 3} is generated and {3, 1} never is. Passing i again allows a candidate to repeat while still forbidding reorderings, which is why combination sum emits {2, 2, 3} once rather than once per arrangement. Passing 0 drops the constraint entirely and you get every ordering of every combination.

Equal values in the input give you the same subset twice

The tree branches on positions, not values, so [2, 2, 3] yields {2} twice and {2, 3} twice: the two 2s are different nodes even though the answers are identical. The fix in the loop-shaped versions is to sort first and then skip a candidate equal to the one just tried at this depth, if (i > start && a[i] == a[i - 1]) continue. In the include-exclude form of subsets the same fix goes on the exclude branch, where after dropping a[i] you advance past every remaining element equal to it before recursing.

Why permutations swap instead of keeping a used array

Swapping needs no second array and no membership test: a[0 until i] is the ordering so far and a[i until n] is exactly what is left, so the undo swap hands the next value of k a clean suffix. The price is order and duplicates. The swap version does not emit in lexicographic order, for [1, 2, 3] it ends 321 then 312, and the sort-then-skip-equal trick above does not apply to it, because swapping an element back destroys the sorted suffix that trick depends on. With repeated values you track the values already tried at this depth instead.

Meet in the middle buys time with memory, and needs a join that is a lookup

The cost is two enumerations of 2^(n/2) plus one sort and a binary search per sum, so n = 40 means about a million sums a side instead of a trillion subsets. Those million sums have to be held, and that is the real ceiling: memory grows at the same rate as time, so n = 60 runs out of space long before it runs out of clock. It also only works when the halves combine through a single key. Subset sum qualifies because a left sum s fixes exactly what is wanted on the right, target - s. A condition that couples the two halves more freely leaves you nothing to look up.

Read more

Next up

Recursion Trees

Divide and conquer over a range

Next lesson: Recursion Trees