Last Stone Weight II
Given an array of stone weights stones, each turn you pick two stones and smash them together (the lighter one is destroyed, the heavier one loses weight equal to the lighter). Return the smallest possible weight of the last remaining stone (or 0 if none remain).
Intuition
Smashing stones is equivalent to assigning each stone a + or - sign and minimising the absolute value of the total. If you think of it as splitting stones into two groups, the result of all smashes is |sum(group1) - sum(group2)|. To minimise this, you want the two groups to be as close in total weight as possible. This is exactly the classic partition problem: find the subset whose sum is as close to totalSum / 2 as possible. A 0/1 knapsack DP with capacity totalSum / 2 solves it.
The key reframing is: smashing stones is assigning +/- signs, and minimising the result is a partition problem. Whenever a problem involves splitting items into two groups to minimise the difference of their sums, it reduces to a subset-sum knapsack with target totalSum / 2. Target sum, equal-partition-sum, and this problem are all the same shape.
Approach
Reduce the problem to a subset-sum partition
Compute totalSum = sum(stones). The answer is totalSum - 2 * bestSubsetSum, where bestSubsetSum is the largest subset sum that does not exceed totalSum // 2. This transforms the smashing simulation into a single optimisation problem.
Solve the bounded subset-sum with a boolean DP
Create a set (or boolean array) dp of reachable sums, starting with {0}. For each stone, for each currently reachable sum s, s + stone is also reachable if it does not exceed target = totalSum // 2. After processing all stones, dp contains every achievable subset sum up to target.
Pick the largest reachable sum and compute the answer
The best subset sum is max(dp). The minimum remaining weight is totalSum - 2 max(dp). Time is O(n totalSum / 2), which for the given constraints (n <= 30, stones[i] <= 100) is at most O(30 * 1500) — very fast. Space is O(totalSum / 2) for the DP set.
Solution
Common pitfalls
Using totalSum as the target instead of totalSum // 2
target = total_sum
target = total_sum // 2
The best subset sum cannot exceed half the total (the other subset has the rest). Using the full sum makes the DP table twice as large and does not improve the answer — subset sums beyond half are mirrors of sums below half.
Iterating the DP forward instead of backward (allowing re-use of stones)
for s in range(stone, target + 1):
dp[s] = dp[s] or dp[s - stone]for s in range(target, stone - 1, -1):
dp[s] = dp[s] or dp[s - stone]Forward iteration lets a stone's weight be added multiple times in the same pass, turning this into an unbounded knapsack. Each stone can only be used once, so iterate backward.
Returning 2 best - total_sum instead of total_sum - 2 best
return 2 * best - total_sum
return total_sum - 2 * best
best <= total_sum / 2, so 2 * best <= total_sum and the difference is non-negative. Swapping the order returns a negative value, which is invalid as a weight.
Edge cases
If even count, they cancel perfectly and the answer is 0. If odd count, one stone remains.
No smashing possible. Return the stone's weight. The DP finds subset sum 0, giving weight - 0 = weight.
The answer is |stones[0] - stones[1]|. The DP finds min(stones[0], stones[1]) as the best subset sum.