327. Last Stone Weight II

Assigning + and - signs to stones and minimizing |sum| is equivalent to splitting them into two groups whose sums are as close as possible. Find the largest achievable subset sum ≤ total/2.

Reduce to subset sum

Each smash is really a ± sign choice; the final stone equals |S1 - S2| where S1 + S2 = total. Minimizing this means making one subset sum s as close to total/2 as possible — then the answer is total - 2s.

Use a boolean subset-sum DP up to total // 2:

dp[0] = True
for stone: for j from target down to stone: dp[j] |= dp[j-stone]
largest s with dp[s] → return total - 2*s

Worked example

[2,7,4,1,8,1] (total 23) → best subset sum 11 → 23 - 22 = 1.

Complexity

• Time: O(n · total).
• Space: O(total).

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 total;
    }
}