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

Meet in the middle over 8 values, target 47.left 0-3right 4-73034142123542527687

Is there a subset of these 8 values adding up to 47? Trying every subset is 2^8 = 256 sums. Instead, cut the array in half: every subset of the whole is a subset of the left half joined to a subset of the right half, so it is enough to list the sums of each half separately and then look for two that meet at 47.

Check your understanding

The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.

  1. How many subset sums does the left half of 4 values produce?

    • 8
    • 16
    • 256

    Answer: 16. Every value is in or out: 2^4 = 16. The whole array would need 2^8 = 256, and 2^(n/2) squared is 2^n, which is the saving in one line.

How it runs, step by step

  1. Is there a subset of these 8 values adding up to 47? Trying every subset is 2^8 = 256 sums. Instead, cut the array in half: every subset of the whole is a subset of the left half joined to a subset of the right half, so it is enough to list the sums of each half separately and then look for two that meet at 47.

    Meet in the middle over 8 values, target 47.

  2. The left half has 4 values, so it has 2^4 = 16 subsets, and the right half has 4, so 16. Two lists of that size replace one list of 256: the exponent is halved, which for large n is the difference between hopeless and quick.

    Each half has about 16 subsets.

  3. Enumerate the left half, 3, 34, 4, 12: its subset sums are 0, 3, 34, 37, 4, 7, 38, 41, 12, 15, 46, 49, 16, 19, 50, 53, in the order the subsets are generated.

    Left half sums listed.

  4. Enumerate the right half, 5, 2, 27, 8, and sort its sums: 0, 2, 5, 7, 8, 10, 13, 15, 27, 29, 32, 34, 35, 37, 40, 42. Sorted once, so every lookup from now on is a binary search rather than a scan.

    Right half sums listed and sorted.

  5. Left subset { } sums to 0, so the right half must supply 47 - 0 = 47. Binary search does not find 47 among the right sums.

    No match for 47.

  6. Left subset {3} sums to 3, so the right half must supply 47 - 3 = 44. Binary search does not find 44 among the right sums.

    No match for 44.

  7. Left subset {34} sums to 34, so the right half must supply 47 - 34 = 13. Binary search finds 13: the right subset {5, 8} meets it, and the two halves together add up to 47.

    Found: 34 plus 13.

  8. Yes: 34 + 5 + 8 = 47, found after 3 lookups. The work was 16 + 16 subset sums and at most 16 binary searches, against 256 subsets by brute force. For 8 values that is a small saving. For 40 values it is about a million operations against a trillion. Meet in the middle applies whenever a solution splits into two independent halves that can be combined by a lookup.

    A subset sums to 47.

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