Last Stone Weight II

medium dp knapsack

Problem

You may smash stones pairwise with optimal pairing. The minimum possible final weight equals |sum1 − sum2| where the stones are partitioned into two subsets. To minimize that, find the largest subset sum ≤ total/2; the answer is total − 2·bestSum.

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

Output1

Total = 23, target = 11. Best subset {1,2,8} sums to 11. Answer = 23 − 22 = 1.

stones (comma-separated)

def last_stone_weight_ii(stones):
    total = sum(stones)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for s in stones:
        for j in range(target, s - 1, -1):
            dp[j] = dp[j] or dp[j - s]
    for j in range(target, -1, -1):
        if dp[j]:
            return total - 2 * j

function lastStoneWeightII(stones) {
  const total = stones.reduce((a, b) => a + b, 0);
  const target = total >> 1;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const s of stones) {
    for (let j = target; j >= s; j--) {
      if (dp[j - s]) dp[j] = true;
    }
  }
  for (let j = target; j >= 0; j--) if (dp[j]) return total - 2 * j;
}

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int s : stones) {
            for (int j = target; j >= s; j--) {
                if (dp[j - s]) dp[j] = true;
            }
        }
        for (int j = target; j >= 0; j--) if (dp[j]) return total - 2 * j;
        return 0;
    }
}

int lastStoneWeightII(vector<int>& stones) {
    int total = 0;
    for (int s : stones) total += s;
    int target = total / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int s : stones) {
        for (int j = target; j >= s; j--) {
            if (dp[j - s]) dp[j] = true;
        }
    }
    for (int j = target; j >= 0; j--) if (dp[j]) return total - 2 * j;
    return 0;
}

Explanation

Smashing stones together until one (or none) remains turns out to be the same as splitting the stones into two piles and minimizing the gap between their sums. The leftover weight is exactly |sum1 - sum2|, so we want the two piles as balanced as possible.

To balance them we aim for one pile as close to total/2 as we can get without going over. That makes this a classic subset-sum knapsack: which sums up to target = total/2 are reachable?

We use a boolean array where dp[j] means "some subset of stones sums to exactly j." Starting from dp[0] = true, we process each stone and update j from high to low so each stone is used at most once.

Finally we scan down from target for the largest reachable sum j and return total - 2*j, the smallest possible final weight.

Example: [2,7,4,1,8,1] has total 23 and target 11. The subset {1,2,8} hits 11 exactly, so the answer is 23 - 22 = 1.

Time: O(n·S) Space: O(S)