Last Stone Weight II

MediumDynamic Programming · 0/1 Knapsack (Subset Sum)🧩 Knapsack DP LeetCode #1049 ↗Updated Oct 30, 2026

Problem

You have stones with positive weights stones[i]. In one move pick any two stones x ≤ y and smash them: equal stones both vanish, otherwise one stone of weight y - x remains. Continue until at most one stone is left. Return the smallest possible weight of that last stone (0 if none remain).

Inputstones = [2,7,4,1,8,1]Output1

Inputstones = [31,26,33,21,40]Output5

1 ≤ stones.length ≤ 30 · 1 ≤ stones[i] ≤ 100

Try it yourself

Java

class Solution {
    public int lastStoneWeightII(int[] stones) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Any sequence of smashes ends with each original weight counted with a + or − sign, and every sign split is achievable. So split the stones into two piles as evenly as possible: find the largest subset sum best ≤ S/2, answer S - 2·best.

PatternKnapsack DP

Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.

Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.

Open the Knapsack DP guide →

Approaches

Brute ForceTry Every Sign Assignment

Time O(2ⁿ)Space O(n)

Give each stone a + or − sign (which pile it joins) and keep the smallest absolute total. This works because the final stone is exactly the difference between the two piles.

Java

public int lastStoneWeightII(int[] stones) {
    return explore(stones, 0, 0);
}

// smallest |diff| reachable after signing stones[i..]
private int explore(int[] stones, int i, int diff) {
    if (i == stones.length) return Math.abs(diff);
    int plus = explore(stones, i + 1, diff + stones[i]);
    int minus = explore(stones, i + 1, diff - stones[i]);
    return Math.min(plus, minus);
}

Simple once the sign insight is known, but 2³⁰ branches is too many.

BetterMemoized Recursion on (index, difference)

Time O(n · S)Space O(n · S)

The running difference always lies in [-S, S], so there are only n · (2S+1) distinct states. Shift the difference by S to use it as an array index and cache each state's answer.

Java

public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int s : stones) total += s;
    Integer[][] memo = new Integer[stones.length][2 * total + 1];
    return explore(stones, 0, 0, total, memo);
}

private int explore(int[] stones, int i, int diff, int total, Integer[][] memo) {
    if (i == stones.length) return Math.abs(diff);
    int key = diff + total; // shift into [0, 2*total]
    if (memo[i][key] != null) return memo[i][key];
    int plus = explore(stones, i + 1, diff + stones[i], total, memo);
    int minus = explore(stones, i + 1, diff - stones[i], total, memo);
    memo[i][key] = Math.min(plus, minus);
    return memo[i][key];
}

Polynomial (30 × 6001 states), but a 2-D table is more than we need.

Optimal1-D Subset-Sum Table

Time O(n · S)Space O(S)

Only the smaller pile matters. can[j] says whether some subset sums to j (for j ≤ S/2). Add stones one at a time, scanning j downward so each stone is used at most once. The largest reachable j gives the answer.

Java

public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int s : stones) total += s;
    int half = total / 2;
    boolean[] can = new boolean[half + 1];
    can[0] = true; // the empty pile
    for (int s : stones) {
        for (int j = half; j >= s; j--) { // downward: 0/1 use
            if (can[j - s]) can[j] = true;
        }
    }
    for (int j = half; j >= 0; j--) {
        if (can[j]) return total - 2 * j;
    }
    return total; // unreachable: can[0] is always true
}

Dry runstones = [2,7,4,1,8,1]

b best sum ≤ S/2 changed

start
T

.

.

.

.

[2,3,4], S=9, half=4
s=2
T

.

T

.

.

can[2] from can[0]
s=3
T

.

T

T

.

can[3]; 5 > half
s=4
T

.

T

T

T

can[4] from can[0]
scan
T

.

T

T

T
b
9 - 2·4 = 1 ✔

Same time as the memo with a single boolean row — the standard answer.

Pro tip

Recognise the disguise: “smash stones” = “partition into two piles with minimum difference”.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Sign Assignment	`O(2ⁿ)`	`O(n)`
Better	Memoized Recursion on (index, difference)	`O(n · S)`	`O(n · S)`
Optimal	1-D Subset-Sum Table	`O(n · S)`	`O(S)`

Common pitfalls

Greedy smashing of the two heaviest stones (as in Last Stone Weight I) is not optimal here.
Scanning j upward in the 1-D table lets a stone be reused.
Forgetting to offset negative differences before using them as array indices.

Interview tips

Spend a minute justifying why every smash order equals a +/− sign assignment.
Then say: this is Partition Equal Subset Sum, but we want the closest-to-half sum.
Mention a BitSet shift-or as a constant-factor speedup.

Pattern

Subset sum / 0-1 knapsack → minimise the difference between two groups of a small-valued set.

My notes saved in this browser