Split the array into two halves, enumerate all 2n/2 subset sums of each, sort one side, and two-pointer / binary-search until the two halves meet: a + b = S.
step 0
The array & the split split
Split at mid: left half (blue) and right half (gold). Every subset of the whole = (a left subset) ∪ (a right subset).
Left half — 23 subset sums (sorted)
Right half — 23 subset sums
Combine: for each right b, look for S − b in the sorted left list
Press Step to begin combining.
left subset right subset match: a + b = S
Press Step to begin. We split the array, enumerate each half's subset sums, sort the left list, then scan the right list looking for the complement S − b.
Self-contained visualization. Brute force would enumerate all 2n subsets; meet-in-the-middle enumerates only 2n/2 per half (the square root) and combines.
See junior.md and professional.md for the split-and-combine correctness proof and the O(2n/2) derivation.