plaintext function lastStoneWeightII(stones) total := sum of all stones target := total / 2 dp := array of size (target + 1), all false dp[0] := true 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: . Space: .
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.