Last Stone Weight II
Medium · Dynamic Programming · Array · Dynamic Programming · Knapsack
Problem
You have a pile of stones, where stones[i] is the weight of stone i. You repeatedly pick any two stones and smash them together. If their weights are x <= y:
- when x == y, both stones are destroyed;
- when x < y, the lighter stone is destroyed and the heavier one now weighs y - x.
You stop when at most one stone is left. You choose which stones to smash each time. Return the smallest possible weight of the stone that remains, or 0 if none remains.
Examples
Input: stones = [2,7,4,1,8,1] Output: 1
The total is 23. Split into {2, 8, 1} (11) and {7, 4, 1} (12): the difference is 1, and an odd total cannot reach 0.
Input: stones = [3,5,8] Output: 0
Smash 3 into 8, leaving 5; then the two 5s destroy each other. In split terms: {3, 5} against {8}.
Input: stones = [100] Output: 100
There is nothing to smash it with.
Constraints
- 1 <= len(stones) <= 30
- 1 <= stones[i] <= 100
Approaches
- Try every split — time O(2^n · n), space O(n)
Follow-up
Python's big integers give a one-line subset-sum table: reach |= reach << w for each stone, with bit s meaning sum s is reachable. The same idea in other languages is a bitset, 64 sums per machine word.
Related problems
Start free on Cariara · Coding problems · System design studio
