DSA problem
Last Stone Weight II
You are given an array of integers stones where stones[i] is the weight of the i-th stone. We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of the smash is: if x == y, both stones are destroyed; otherwise, the stone of weight x is destroyed and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the smallest possible weight of the left stone, or 0 if there are no stones left.
The greedy heap simulation (always smashing the two heaviest stones together) solves the basic "Last Stone Weight" variant but fails here because we are now allowed to combine stones in any order, and order matters for the final weight. The key insight is that each smash sequence corresponds to assigning each stone a sign of + or - — the final weight equals the absolute value of the signed sum.
So the problem reduces to partitioning stones into two disjoint groups A and B such that |sum(A) - sum(B)| is minimized. Equivalently, we want to choose a subset A with sum(A) as close to sum(stones) / 2 as possible, since then the other half is sum - sum(A) and the gap is sum - 2 * sum(A).
This is a classic 0/1 knapsack reachability problem. Build a boolean DP over capacities 0 to sum / 2, where dp[s] is true if some subset sums to exactly s. The largest reachable s <= sum / 2 gives the best partition, and the answer is sum - 2 * s. The full algorithm is O(n * sum) time and O(sum) space, well within the constraints.
Examples
stones = [2,7,4,1,8,1]1stones = [31,26,33,21,40]5stones = [1,2]1Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
- The total sum of all stones is bounded by ~3000, keeping the DP tractable.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.