Last Stone Weight II

How it works

A bitset can represent reachable sums more compactly than a hash set. Each bit position represents whether that sum is achievable. Shifting the bitset left by a stone's weight and OR-ing with the original efficiently computes all new reachable sums in a single operation.

Steps

1. Initialize a bitset with only bit 0 set (sum 0 is reachable).
2. For each stone, left-shift the bitset by the stone's weight and OR it with itself.
3. Starting from target down to 0, find the first set bit. This represents the largest achievable sum not exceeding target.
4. Return stoneSum - 2 * t.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(m)

Where n is the number of stones and m is the sum of the weights of the stones.

Things to watch for

Not Recognizing the Subset Sum Connection

The problem appears to be about simulating stone collisions, but it is actually a partition problem. The key insight is that the final result equals the absolute difference between two groups of stones. Missing this connection leads to inefficient simulation approaches that fail on larger inputs.

Incorrect Target Calculation

The target should be stoneSum // 2 (floor division), representing the largest possible sum for one partition. Using ceiling division or forgetting to halve the sum leads to incorrect DP table dimensions or wrong final calculations.

Forward Iteration in Space-Optimized DP

In the 1D DP approach, iterating from 0 to target instead of from target down to stone causes each stone to be counted multiple times. This happens because updated values at lower indices affect higher indices within the same iteration, violating the 0/1 knapsack constraint.

from typing import List

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        stoneSum = sum(stones)
        target = stoneSum // 2
        dp = 1

        for stone in stones:
            dp |= dp << stone

        for t in range(target, -1, -1):
            if dp & (1 << t):
                return stoneSum - 2 * t

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int stoneSum = accumulate(stones.begin(), stones.end(), 0);
        int target = stoneSum / 2;
        bitset<3001> dp;
        dp[0] = true;

        for (int stone : stones) {
            dp |= (dp << stone);
        }

        for (int t = target; t >= 0; --t) {
            if (dp[t]) {
                return stoneSum - 2 * t;
            }
        }
        return 0;
    }
};