meet in the middle

Searching all 2^n subsets of n items is hopeless once n passes the low thirties. Meet in the middle is a clever trick that often cuts the exponent in half: instead of enumerating the whole space at once, split the items into two halves of n/2 each, enumerate every subset of each half separately, and then combine the two lists cleverly to find a matching pair. You do two manageable searches of size 2^(n/2) and join them, rather than one impossible search of size 2^n.

Subset-sum makes it concrete. You want a subset of the n numbers summing to target T. Split the numbers into halves L and R. Enumerate all 2^(n/2) subset-sums of L into a list, and all 2^(n/2) subset-sums of R into another list. Any full solution uses some subset of L summing to a and some subset of R summing to b with a + b = T. So sort the R-sums, and for each sum a in the L-list, binary-search the R-list for the value T - a; a hit means you found two halves that combine to T. The cost is 2^(n/2) to build each list plus 2^(n/2) log(2^(n/2)) to sort and search, i.e. roughly O(2^(n/2) * n) — dramatically better than 2^n. For n = 40, 2^40 is about 10^12 but 2^20 is only about 10^6, the difference between intractable and instant.

Meet in the middle is the go-to upgrade for exponential problems with two combinable halves: subset-sum, k-sum, finding a collision, and certain knapsack and cryptographic searches. Its requirements are real, though: you need to be able to split the problem so that solutions decompose into an L-part and an R-part that can be matched (here, sums simply add), and you pay in memory — storing 2^(n/2) partial results is itself exponential, just with a halved exponent. It does not make the problem polynomial; it square-roots the exponential, which is often exactly the boost that turns hopeless into doable.