Last Stone Weight II: Subset Sum DP Pattern

You have a collection of stones, each with a positive integer weight. On each turn, you pick any two stones and smash them together. If they have the same weight, both are destroyed. If they have different weights, the smaller one is destroyed and the larger one has its weight reduced by the weight of the smaller one. Return the smallest possible weight of the last remaining stone. If all stones are destroyed, return 0.

This is LeetCode 1049: Last Stone Weight II, and at first glance it looks like a simulation problem. But simulating every possible pair of smashes leads to an exponential search. The real insight is that this problem reduces to a partition problem, and from there it becomes a clean subset sum DP.

Why this reduces to partitioning

Think about what happens when you smash stones together. Each stone's weight is either added or subtracted in the final result. If you have stones [a, b, c, d], any sequence of smashes produces a result of the form +/-a +/-b +/-c +/-d. The sign of each stone depends on which "side" it ends up on during the chain of collisions.

This means the problem is equivalent to: split the stones into two groups and minimize the absolute difference of their sums. If group A sums to sumA and group B sums to sumB, the last stone weight is |sumA - sumB|.

To minimize that difference, you want one group's sum to be as close to total / 2 as possible. So the question becomes: what is the largest sum you can form that does not exceed total / 2? That is a classic subset sum problem.

If the best reachable sum at or below total / 2 is best, then:

• Group A sums to best
• Group B sums to total - best
• The answer is total - 2 * best

The solution

def last_stone_weight_ii(stones: list[int]) -> int:
    total = sum(stones)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for stone in stones:
        for j in range(target, stone - 1, -1):
            if dp[j - stone]:
                dp[j] = True

    for j in range(target, -1, -1):
        if dp[j]:
            return total - 2 * j

    return total

Let's walk through how this works.

The dp array is a boolean array where dp[j] means "can we form a subset of stones that sums to exactly j?" We initialize dp[0] = True because the empty subset always sums to zero.

For each stone, we iterate backward from target down to stone. This backward direction is critical: it ensures each stone is used at most once, which is the hallmark of the 0/1 knapsack pattern. If dp[j - stone] is already True, then adding this stone lets us reach sum j, so we set dp[j] = True.

After processing all stones, we scan from target downward to find the largest reachable sum. That value is best, and the answer is total - 2 * best.

The final return total is a safety fallback that never actually triggers (since dp[0] is always True, the loop always finds at least j = 0).

Visual walkthrough

Let's trace through stones = [2, 7, 4, 1, 8, 1] where total = 23 and target = 11. Watch the set of reachable sums grow as we process each stone.

After processing all stones, the largest reachable sum at or below 11 is 11 itself. The answer is 23 - 2 * 11 = 1. That matches our partition: group A = = 11, group B = = 12, and the difference is 1.

Complexity analysis

Time is O(n * target) where n is the number of stones and target is total / 2. For each stone, we scan the entire DP array once. With LeetCode constraints (up to 30 stones, weights up to 100), target can be at most 1500. That gives 30 * 1500 = 45,000 operations, which runs instantly.

Space is O(target) for the single boolean array. No 2D table needed thanks to the 1D optimization with backward iteration.

The building blocks

1. Subset sum reachability DP

The core pattern: maintain a boolean array dp where dp[j] tracks whether sum j is achievable from the elements processed so far. Initialize dp[0] = True. For each element, iterate backward and propagate reachability.

dp = [False] * (target + 1)
dp[0] = True

for num in nums:
    for j in range(target, num - 1, -1):
        if dp[j - num]:
            dp[j] = True

This building block appears in Partition Equal Subset Sum (LeetCode 416), Target Sum (LeetCode 494), and any problem that asks "which sums can I form from this set of numbers?" The backward loop enforces the 0/1 constraint, preventing any element from being used more than once.

2. Partition minimization reduction

The pattern of reducing "minimize the difference between two groups" to "find a subset sum closest to half the total." Once you have the reachability array, scan downward from target to find the best achievable sum.

for j in range(target, -1, -1):
    if dp[j]:
        return total - 2 * j

This reduction is the conceptual leap in Last Stone Weight II. You see a stone-smashing simulation and recognize it as a partition problem. The same reduction applies whenever a problem asks you to split items into two groups and optimize the difference.

Edge cases

Before submitting, think through these scenarios:

• Single stone: return its weight. There is nothing to smash it with.
• Two stones: return the absolute difference of their weights.
• All stones equal: if there is an even number, they all cancel out and the answer is 0. If odd, one stone remains.
• One very large stone: e.g., [1, 1, 1, 100]. The best you can do is 100 - 1 - 1 - 1 = 97. The DP naturally finds that the closest reachable sum to target is 3.
• Total is even and a perfect split exists: the answer is 0. The DP will find dp[total / 2] = True.

From understanding to recall

You now see how Last Stone Weight II reduces to a subset sum DP. The logic is clean: build a reachability array, find the best sum at or below half the total, and compute the difference. But recognizing the partition reduction under interview pressure is the hard part.

The details that matter are small. Do you iterate the inner loop forward or backward? Do you return total - 2 * best or total - best? Do you set target to total / 2 or (total + 1) / 2? These are not gaps in understanding. They are gaps in recall, and spaced repetition is how you close them.

You practice writing the subset sum DP from scratch, the backward loop, the partition reduction, and the final scan. After a few spaced reps, the pattern is automatic. You see "minimize remaining weight" or "split into two groups" in a problem description, and the 0/1 knapsack template flows out without hesitation.

Related posts

• Partition Equal Subset Sum - The foundational subset sum DP problem, asking whether you can split an array into two equal halves
• Target Sum - Another partition reduction where you assign + or - to each element to reach a target, using the same subset sum DP
• Coin Change - Unbounded knapsack DP where the inner loop goes forward instead of backward, a key contrast with the 0/1 pattern used here

CodeBricks breaks Last Stone Weight II into its subset sum reachability and partition minimization building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a partition DP problem shows up in your interview, you do not think about it. You just write it.