Meet in the Middle - Example

Problem: Find if any subset of $40$ numbers sums to target.

$1.$ Split into two halves of $20$.

$2.$ Generate all $2^{20}$ sums for each half.

$3.$ Sort second half. For each sum $s$ in first half, binary search for $target - s$.

for s in firstHalfSums:
    if binarySearch(secondHalfSums, target - s):
        return true

Time: $O(2^{n/2} \cdot n)$ instead of $O(2^n)$. For $n=40$: $10^7$ vs $10^{12}$.