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.
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.
How many subset sums does the left half of 4 values produce?
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
Related
Where this is used
DatabasesPostgreSQL choosing a join order
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.
SecurityMeet in the middle against double DES
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.
Standard librariesPython's itertools
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.
CompilersSuperoptimizers
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
- Power setWikipedia
- Heap's algorithmWikipedia
- Generating all K-combinationscp-algorithms
- Meet-in-the-middle attackWikipedia
- itertools: combinations, permutations and the powerset recipePython docs · docs.python.org