#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack-variations/last-stone-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack-variations/last-stone-implementation

Repovive

LeetCode 1049 Last Stone Weight II - Implementation - Knapsack Variations | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 1049 Last Stone Weight II - Implementation

The code

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.