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.
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.
Including 1 leaves 2 elements to decide. How many subsets come out of this branch?
Answer: 4. Each remaining element doubles the count: 2 to the 2 = 4. The exclude branch will produce the same number again.
Including 2 leaves 1 element to decide. How many subsets come out of this branch?
Answer: 2. Each remaining element doubles the count: 2 to the 1 = 2. The exclude branch will produce the same number again.
Including 3 leaves 0 elements to decide. How many subsets come out of this branch?
Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.
Including 3 leaves 0 elements to decide. How many subsets come out of this branch?
Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.
Including 2 leaves 1 element to decide. How many subsets come out of this branch?
Answer: 2. Each remaining element doubles the count: 2 to the 1 = 2. The exclude branch will produce the same number again.
Including 3 leaves 0 elements to decide. How many subsets come out of this branch?
Answer: 1. Each remaining element doubles the count: 2 to the 0 = 1. The exclude branch will produce the same number again.
Including 3 leaves 0 elements to decide. How many subsets come out of this branch?
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
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.
Element 0 is 1. First branch: include it, chosen is now {1}. Go deeper.
Include 1 and recurse.
Element 1 is 2. First branch: include it, chosen is now {1, 2}. Go deeper.
Include 2 and recurse.
Element 2 is 3. First branch: include it, chosen is now {1, 2, 3}. Go deeper.
Include 3 and recurse.
Past the last element: a leaf. Subset 1: {1, 2, 3}.
Leaf. Subset 1 is {1, 2, 3}.
Back at element 2. Undo: drop 3, chosen is {1, 2}. Second branch: exclude it and go deeper.
Exclude 3 and recurse.
Past the last element: a leaf. Subset 2: {1, 2}.
Leaf. Subset 2 is {1, 2}.
Back at element 1. Undo: drop 2, chosen is {1}. Second branch: exclude it and go deeper.
Exclude 2 and recurse.
Element 2 is 3. First branch: include it, chosen is now {1, 3}. Go deeper.
Include 3 and recurse.
Past the last element: a leaf. Subset 3: {1, 3}.
Leaf. Subset 3 is {1, 3}.
Back at element 2. Undo: drop 3, chosen is {1}. Second branch: exclude it and go deeper.
Exclude 3 and recurse.
Past the last element: a leaf. Subset 4: {1}.
Leaf. Subset 4 is {1}.
Back at element 0. Undo: drop 1, chosen is { }. Second branch: exclude it and go deeper.
Exclude 1 and recurse.
Element 1 is 2. First branch: include it, chosen is now {2}. Go deeper.
Include 2 and recurse.
Element 2 is 3. First branch: include it, chosen is now {2, 3}. Go deeper.
Include 3 and recurse.
Past the last element: a leaf. Subset 5: {2, 3}.
Leaf. Subset 5 is {2, 3}.
Back at element 2. Undo: drop 3, chosen is {2}. Second branch: exclude it and go deeper.
Exclude 3 and recurse.
Past the last element: a leaf. Subset 6: {2}.
Leaf. Subset 6 is {2}.
Back at element 1. Undo: drop 2, chosen is { }. Second branch: exclude it and go deeper.
Exclude 2 and recurse.
Element 2 is 3. First branch: include it, chosen is now {3}. Go deeper.
Include 3 and recurse.
Past the last element: a leaf. Subset 7: {3}.
Leaf. Subset 7 is {3}.
Back at element 2. Undo: drop 3, chosen is { }. Second branch: exclude it and go deeper.
Exclude 3 and recurse.
Past the last element: a leaf. Subset 8: { }.
Leaf. Subset 8 is { }.
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.
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