Meet in the Middle
Split the input in two, enumerate each half, combine with sorting or hashing; 2^(n/2) instead of 2^n.
Decision · step 2 of 8Enumeration: Two half-enumerations meet at the target
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.
What you will see
Two half-enumerations meet in a sorted merge or a hash lookup.
Cost
| Best | O(2^(n/2)) |
|---|---|
| Average | O(2^(n/2) * n) |
| Worst | O(2^(n/2) * n) |
| Space | O(2^(n/2)) |
How you work with it here
play it through, step one change at a time, run it on your own input, predict what happens next.
Screen readers: Pattern lessons reuse the canonical algorithm's semantics and add a spoken "recognize this when" cue.
Reduced motion: Inherits the canonical algorithm's strategy.
Taught by the same lesson
Enumeration covers these too, in the same run.