LeetCode 1049 Last Stone Weight II - Implementation

function lastStoneWeightII(stones)
    total := sum of all stones
    target := total / 2
    dp := array of size (target + 1), all false
    dp[0] := true
    for each stone in stones
        for s from target down to stone
            dp[s] := dp[s] OR dp[s - stone]
    // Find largest achievable sum <= target
    best := 0
    for s from target down to 0
        if dp[s]
            best := s
            break
    return total - 2 * best

Time: $O(n \times sum)$. Space: $O(sum)$.

You find the largest subset sum that doesn't exceed half the total. The remaining stones sum to total - best. The difference between the two groups is total - 2 * best.

This is partition with optimization instead of exact matching. The greedy approach of always smashing the two largest stones doesn't work. DP finds the global optimum.