##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Splitting search to reduce complexity.
Meet in the middle: split problem, solve halves, combine.
Subset sum: Find if any subset sums to target.
Brute force: 2n subsets. n=40⇒1012. Too slow.
Meet in middle: 1. Split into halves of 20.
2. Generate 220 sums each.
3. For sum s in first, check if target−s in second (hash set).
Time: O(2n/2⋅n). For n=40: ∼4×107. Feasible.
