Meet in the Middle: The Interview Trick That Turns 2^40 Into 2^20
2 views
Some interview problems look like plain brute force until you notice the input size. When n is around 40 and the task is "count subsets whose sum is at most K" or "find the subset sum closest to a target", enumerating all 2^40 subsets (about a trillion) is hopeless. Classic dynamic programming also fails if the values are huge, because a DP table indexed by sum would be astronomically large. This is exactly where meet in the middle shines.
The idea
Split the array into two halves, A and B, each of size about n/2. Enumerate every subset sum of A and every subset sum of B separately. Each half has only 2^20, roughly one million, subsets. Now any subset of the full array is just one subset of A combined with one subset of B, so the original question becomes a question about pairs: for each sum a in the first list, which sums b in the second list satisfy a + b <= K, or make a + b closest to the target?
Combining efficiently
Sort the second list. For each value a, binary search for the largest b with b <= K - a; the number of valid partners is that index plus one. Total cost is O(2^(n/2) * n), which runs in well under a second. For "closest to target" you can either binary search per element or use two pointers: sort both lists, put one pointer at the start of the first list and one at the end of the second, and move them inward depending on whether the current sum is above or below the target.
Generating subset sums cleanly
A neat way to build all subset sums of a half is iterative: start with [0], and for each element x, append x + s for every existing sum s. This produces 2^k sums for k elements without recursion. If you build each half this way and keep the lists sorted while merging, you can even avoid a separate sort.
Where interviewers use it
Typical prompts include partitioning an array into two groups with minimal difference (LeetCode 2035), 4-sum style counting where you precompute pair sums, and bidirectional search on graphs, which is the same philosophy applied to BFS: search from the start and from the goal and stop when the frontiers meet.
How to talk about it in the interview
State the brute-force complexity first, then point out that n is small but not small enough. Say explicitly: "I'll split the input into two halves, enumerate each in 2^(n/2), and combine with sorting plus binary search." Interviewers reward candidates who connect the constraint to the technique. Mention the memory cost too, since two lists of a million integers is fine but worth noting.
Practicing this kind of reasoning under time pressure is the hard part. If you want support during the real thing, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, so you can stay focused on explaining the trade-offs clearly instead of freezing on the approach.