Meet in the Middle

Meet in the middle: split problem, solve halves, combine.

Subset sum: Find if any subset sums to target.

Brute force: $2^n$ subsets. $n=40 \Rightarrow 10^{12}$. Too slow.

Meet in middle: $1.$ Split into halves of $20$.

$2.$ Generate $2^{20}$ sums each.

$3.$ For sum $s$ in first, check if $target-s$ in second (hash set).

Time: $O(2^{n/2} \cdot n)$. For $n=40$: $\sim 4 \times 10^7$. Feasible.