Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumknapsack-subset-dp

Last Stone Weight II

Problem (restated)

Smash two stones a,b: if a≠b a stone of |a-b| remains. Minimize the final stone weight (0 if none).

Intuition

Equivalent to partition stones into two piles with sums as equal as possible; answer is |sum-2S| for best subset sum S ≤ sum/2.

Approaches

Partition closest to half

Tested only

Time O(n·Σ)Space O(Σ)

Idea. Boolean subset-sum DP to target=sum/2; take largest achievable s; return sum-2s.

Walkthrough. [2,7,4,1,8,1] → 1.

Trade-offs. Same core as Partition Equal Subset Sum; minimize difference instead of checking equality.

Solution

export function lastStoneWeightII(stones: number[]): number {
  const total = stones.reduce((a, b) => a + b, 0);
  const target = Math.floor(total / 2);
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of stones) {
    for (let c = target; c >= x; c--) dp[c] = dp[c] || dp[c - x];
  }
  for (let s = target; s >= 0; s--) if (dp[s]) return total - 2 * s;
  return total;
}

export function lastStoneWeightII(stones: number[]): number {
  const total = stones.reduce((a, b) => a + b, 0);
  const target = Math.floor(total / 2);
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of stones) {
    for (let c = target; c >= x; c--) dp[c] = dp[c] || dp[c - x];
  }
  for (let s = target; s >= 0; s--) if (dp[s]) return total - 2 * s;
  return total;
}

Template connection

Subset-sum / partition DP.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?