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 ordering of 1, 2, 3. Fix position 0 by swapping each element into it in turn, recurse on the rest, and swap back so the next choice starts from the same array. Every leaf is one permutation: 3! = 6 of them.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.
Position 0 is next, with 1, 2, 3 still to place. Which value goes in first?
Answer: 1. Candidates are tried in array order, and 1 is next in line.
Position 1 is next, with 2, 3 still to place. Which value goes in first?
Answer: 2. Candidates are tried in array order, and 2 is next in line.
Position 1 is next, with 3, 2 still to place. Which value goes in first?
Answer: 3. Candidates are tried in array order, and 3 is next in line.
Position 0 is next, with 2, 1, 3 still to place. Which value goes in first?
Answer: 2. Candidates are tried in array order, and 2 is next in line.
Position 1 is next, with 1, 3 still to place. Which value goes in first?
Answer: 1. Candidates are tried in array order, and 1 is next in line.
Position 1 is next, with 3, 1 still to place. Which value goes in first?
Answer: 3. Candidates are tried in array order, and 3 is next in line.
Position 0 is next, with 3, 2, 1 still to place. Which value goes in first?
Answer: 3. Candidates are tried in array order, and 3 is next in line.
Position 1 is next, with 2, 1 still to place. Which value goes in first?
Answer: 2. Candidates are tried in array order, and 2 is next in line.
Position 1 is next, with 1, 2 still to place. Which value goes in first?
Answer: 1. Candidates are tried in array order, and 1 is next in line.
How it runs, step by step
Every ordering of 1, 2, 3. Fix position 0 by swapping each element into it in turn, recurse on the rest, and swap back so the next choice starts from the same array. Every leaf is one permutation: 3! = 6 of them.
Generating all permutations of 3 values by swapping each candidate into each position.
Position 0: keep 1 where it is and fix it. Recurse on positions 1 onward.
Position 0 takes 1.
Position 1: keep 2 where it is and fix it. Recurse on positions 2 onward.
Position 1 takes 2.
Position 2: keep 3 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 3.
Every position is fixed: a leaf. Permutation 1: 1 2 3.
Leaf. Permutation 1 is 1 2 3.
Back at position 1. Nothing to undo for 2; try the next candidate.
Undo the swap at position 1.
Position 1: swap 3 in from position 2 and fix it. Recurse on positions 2 onward.
Position 1 takes 3.
Position 2: keep 2 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 2.
Every position is fixed: a leaf. Permutation 2: 1 3 2.
Leaf. Permutation 2 is 1 3 2.
Back at position 1. Swap 3 back out so the array is as it was, then try the next candidate.
Undo the swap at position 1.
Back at position 0. Nothing to undo for 1; try the next candidate.
Undo the swap at position 0.
Position 0: swap 2 in from position 1 and fix it. Recurse on positions 1 onward.
Position 0 takes 2.
Position 1: keep 1 where it is and fix it. Recurse on positions 2 onward.
Position 1 takes 1.
Position 2: keep 3 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 3.
Every position is fixed: a leaf. Permutation 3: 2 1 3.
Leaf. Permutation 3 is 2 1 3.
Back at position 1. Nothing to undo for 1; try the next candidate.
Undo the swap at position 1.
Position 1: swap 3 in from position 2 and fix it. Recurse on positions 2 onward.
Position 1 takes 3.
Position 2: keep 1 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 1.
Every position is fixed: a leaf. Permutation 4: 2 3 1.
Leaf. Permutation 4 is 2 3 1.
Back at position 1. Swap 3 back out so the array is as it was, then try the next candidate.
Undo the swap at position 1.
Back at position 0. Swap 2 back out so the array is as it was, then try the next candidate.
Undo the swap at position 0.
Position 0: swap 3 in from position 2 and fix it. Recurse on positions 1 onward.
Position 0 takes 3.
Position 1: keep 2 where it is and fix it. Recurse on positions 2 onward.
Position 1 takes 2.
Position 2: keep 1 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 1.
Every position is fixed: a leaf. Permutation 5: 3 2 1.
Leaf. Permutation 5 is 3 2 1.
Back at position 1. Nothing to undo for 2; try the next candidate.
Undo the swap at position 1.
Position 1: swap 1 in from position 2 and fix it. Recurse on positions 2 onward.
Position 1 takes 1.
Position 2: keep 2 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 2.
Every position is fixed: a leaf. Permutation 6: 3 1 2.
Leaf. Permutation 6 is 3 1 2.
Back at position 1. Swap 1 back out so the array is as it was, then try the next candidate.
Undo the swap at position 1.
Back at position 0. Swap 3 back out so the array is as it was, then try the next candidate.
Undo the swap at position 0.
6 permutations: 1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 2 1 | 3 1 2. Each level of the recursion has one fewer candidate, so the leaves number 3!, and every swap was undone: 10 swaps, the array ends as it began.
6 permutations 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