AlgoScope

Meet in the Middle

Split the input in two, enumerate each half, combine with sorting or hashing. 2^(n/2) instead of 2^n.

Problem-solving patterns, pattern, advanced
Each half has about 16 subsets.left 0-3right 4-73034142123542527687
Each half has about 16 subsets.left 0-3right 4-73034142123542527687

Enumeration: Two half-enumerations meet at the target

Decision, step 2 of 8

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.

How enumeration works

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.