Meet in the Middle
Split the input in two, enumerate each half, combine with sorting or hashing. 2^(n/2) instead of 2^n.
Enumeration: 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.
Cost
- Best
- O(2^(n/2))
- Average
- O(2^(n/2) * n)
- Worst
- O(2^(n/2) * n)
- Space
- O(2^(n/2))
Taught by the same lesson
Enumeration covers these too, in the same run.