LeetCode 1049: Last Stone Weight II

Problem Restatement

We have a collection of stones with integer weights.

In each step, we take two stones and smash them together. If their weights are x and y with x <= y, we get a stone of weight y - x.

We need to return the smallest possible weight of the remaining stone (or 0 if none remain).

The official constraints state that 1 <= stones.length <= 30 and 1 <= stones[i] <= 100.

Input and Output

Function shape:

def lastStoneWeightII(stones: list[int]) -> int:
    ...

Examples

Example 1:

stones = [2, 7, 4, 1, 8, 1]

sum = 23. We can achieve a minimum weight of 1.

Answer:

1

Key Insight

The smashing process is equivalent to assigning + or - signs to each stone weight and taking the absolute value of the sum.

We want to partition the stones into two groups S1 and S2 to minimize |S1 - S2|.

This is a 0/1 knapsack problem: find the largest achievable sum ≤ total // 2.

The answer is total - 2 * best_sum.

Algorithm

1. Compute total = sum(stones).
2. DP: find all achievable sums up to total // 2.
3. Find the largest achievable sum ≤ total // 2.
4. Return total - 2 * best.

Correctness

Every partition into two groups corresponds to a subset sum. Minimizing |S1 - S2| is equivalent to finding a subset summing to as close to total / 2 as possible.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def lastStoneWeightII(self, stones: list[int]) -> int:
        total = sum(stones)
        target = total // 2
        dp = {0}

        for stone in stones:
            dp = {s + stone for s in dp} | dp
            dp = {s for s in dp if s <= target}

        best = max(dp)
        return total - 2 * best

Code Explanation

We maintain the set of all achievable sums up to target:

dp = {s + stone for s in dp} | dp

Adding each stone creates new achievable sums. We keep only those ≤ target.

The answer is:

return total - 2 * best

Where best is the largest achievable partial sum.

Testing

def run_tests():
    s = Solution()

    assert s.lastStoneWeightII([2, 7, 4, 1, 8, 1]) == 1
    assert s.lastStoneWeightII([31, 26, 33, 21, 40]) == 5
    assert s.lastStoneWeightII([1, 2]) == 1

    print("all tests passed")

run_tests()