LeetCode 1049 Last Stone Weight II - Hidden Subset Sum

Here's the key: smashing is just assigning + or - signs to stones. When you smash $x$ and $y$, the result is $|x - y|$. If you trace through all smashes, the final result is $|\sum_{+} - \sum_{-}|$.

So the problem becomes: partition stones into two groups to find the smallest absolute difference of their sums. If total sum is $S$, and one group sums to $P$, the difference is $|P - (S - P)| = |2P - S|$. To reduce this, find the largest $P \leq S/2$ that's achievable. That's subset sum! Run boolean DP up to $S/2$, find the largest true value, and compute $S - 2P$.