LeetCode 1049 Last Stone Weight II - Walkthrough

Trace Last Stone Weight II on $[2, 7, 4, 1, 8, 1]$. Total sum is $23$. The insight: smashing stones is like assigning $+$ or $-$ signs. Find the lowest $|P - N|$ where $P + N = 23$. Find the largest subset sum $\leq 23/2 = 11$. Using DP: achievable sums include $\{1, 2, 3, 4, 5, 7, 8, 9, 11,...\}$. Largest sum $\leq 11$ is $11$ (e.g., $7 + 4 = 11$).

Answer: $23 - 2 \times 11 = 1$. The goal is to find the smallest absolute difference, which connects directly to partitioning into equal halves.