Last Stone Weight II
The briefingthe full drill, in my own words
The drill: Stones get smashed together two at a time — the heavier one survives, reduced by the lighter one's weight, and equal weights destroy both. Choosing the smashing order freely, find the smallest possible weight the last stone can end up with.
A collection of stone weights arrives, and stones get smashed together two at a time: the heavier stone survives, reduced by the lighter stone's weight, while equal weights destroy each other completely.
Which two stones get smashed together at each step is entirely up to the chooser, and the order can be picked freely to try to leave the smallest possible weight behind at the very end.
The task is to find that smallest achievable final weight — either a single stone's leftover weight, or zero if every stone cancels out completely.
- stone weights are positive integers
- arrays run up to a few dozen stones
- smashing order can be chosen freely to minimize the result
- the final weight is zero when everything cancels out exactly
The hintstake only what you need
HINT 1 THE NUDGE
However the smashing plays out, every stone ends up contributing to one of exactly two totals — the two 'sides' that keep colliding into whatever survives. The final weight is just the difference between those two sides.
HINT 2 THE STRUCTURE
So the real question isn't about smashing order at all: split the stones into two groups so their sums land as close together as possible. That's a subset-sum question wearing a costume.
HINT 3 ONE STEP FROM THE ANSWER
Let target = total // 2. Find the largest achievable subset sum ≤ target with a reachability DP over sums 0..target — the answer is total − 2 × that best reachable sum.
Coach's boardthe pattern, step by step
stones=[2,4,5], total=11, target=11//2=5. reachable[0]=true from the start — zero needs no stones at all.
The splitstwo paces, two languages
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
target = total // 2
reachable = [False] * (target + 1)
reachable[0] = True
for s in stones:
for t in range(target, s - 1, -1):
if reachable[t - s]:
reachable[t] = True
best = next(t for t in range(target, -1, -1) if reachable[t])
return total - 2 * bestclass Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
n = len(stones)
best = total # everything on one side, nothing on the other
for mask in range(1 << n):
side = 0
for i in range(n):
if mask & (1 << i):
side += stones[i]
best = min(best, abs(total - 2 * side))
return bestclass Solution {
public int lastStoneWeightII(int[] stones) {
int total = 0;
for (int s : stones) {
total += s;
}
int target = total / 2;
boolean[] reachable = new boolean[target + 1];
reachable[0] = true;
for (int s : stones) {
for (int t = target; t >= s; t--) {
if (reachable[t - s]) {
reachable[t] = true;
}
}
}
int best = 0;
for (int t = target; t >= 0; t--) {
if (reachable[t]) {
best = t;
break;
}
}
return total - 2 * best;
}
}class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length;
int total = 0;
for (int s : stones) {
total += s;
}
int best = total;
for (int mask = 0; mask < (1 << n); mask++) {
int side = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
side += stones[i];
}
}
best = Math.min(best, Math.abs(total - 2 * side));
}
return best;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED