Last Stone Weight II

The crucial insight behind this problem is understanding what the smashing process actually computes.

When you smash two stones with weights x and y, you get |y − x|. If you then smash the result with another stone z, you get something like |z − |y − x||. Expanding this out, each original stone weight ends up with either a + or − sign in front of it.

For example, with stones [a, b, c, d], the final result after all smashing could be expressions like +a − b + c − d or −a + b − c + d, depending on how you pair them. Every possible smashing sequence corresponds to assigning each stone a + or − sign.

This means the problem is equivalent to: partition the stones into two groups (Group+ and Group−) to minimize |sum(Group+) − sum(Group−)|.

If the total sum is S, and one group has sum P, the other group has sum S − P. The final weight is |S − 2P|. To minimize this, we want P as close to S/2 as possible.

The brute force approach simply tries all possible assignments of + and − to each stone and returns the minimum absolute result.

Let's trace through stones = [2, 7, 4, 1, 8, 1] with the brute force approach:

Step 1: Calculate total sum: 2 + 7 + 4 + 1 + 8 + 1 = 23. We want to split stones into two groups with sums as close to 23/2 = 11.5 as possible. Since all weights are integers, the best achievable difference is 1 (groups of 11 and 12).

Step 2: Try assignment (+2, +7, +4, +1, −8, −1): sum = 2+7+4+1−8−1 = 5. Not minimal.

• Running minimum: 5

Step 3: Try assignment (+2, −7, +4, +1, −8, +1): sum = 2−7+4+1−8+1 = −7, |−7| = 7. Worse.

• Running minimum: 5

Step 4: Try assignment (+2, +7, +4, −1, −8, −1): sum = 2+7+4−1−8−1 = 3. Better!

• Running minimum: 3

Step 5: Try assignment (−2, +7, +4, −1, −8, +1): sum = −2+7+4−1−8+1 = 1. Excellent!

• Running minimum: 1. This corresponds to Group+ = {7, 4, 1} (sum 12), Group− = {2, 1, 8} (sum 11).

Step 6: Can we achieve 0? That would require a group summing to exactly 11.5, which is impossible with integer weights. So 1 is the theoretical minimum for odd total sum.

Step 7: But brute force doesn't know this — it must check ALL 2^6 = 64 sign assignments to be sure. With 30 stones (constraint max), that's 2^30 ≈ 1.07 billion combinations — dangerously slow.

Step 8: Final answer: 1.

1. Define dfs(index, currentSum) that recursively assigns + or − to each stone
2. Base case: If index == n, return |currentSum| — the final stone weight for this assignment
3. Recursive case:
   • Assign +: add = dfs(index + 1, currentSum + stones[index])
   • Assign −: sub = dfs(index + 1, currentSum − stones[index])
   • Return min(add, sub)
4. Call dfs(0, 0)

Time Complexity: O(2^n)

Each stone gets two choices (+ or −), creating a binary tree of depth n. The total number of leaf nodes is 2^n. With n up to 30, that's over a billion operations — too slow.

Space Complexity: O(n)

The recursion stack can go n levels deep (one level per stone). No additional data structures are used.

We reformulate the problem as a 0/1 Knapsack:

• Items: Each stone, with weight = value = stones[i]
• Knapsack capacity: target = totalSum / 2
• Goal: Maximize the total weight we can fit in the knapsack

We build a 2D table dp[i][j] where:

• i = number of stones considered so far (0 to n)
• j = remaining knapsack capacity (0 to target)
• dp[i][j] = maximum sum achievable using the first i stones with capacity limit j

For each stone, we have two choices:

1. Don't take it: dp[i][j] = dp[i-1][j] — same result as without this stone
2. Take it (if it fits): dp[i][j] = dp[i-1][j - stones[i-1]] + stones[i-1] — add stone's weight to best result with remaining capacity

We choose whichever option gives a larger sum.

After filling the table, dp[n][target] gives the maximum subset sum ≤ S/2. The minimum final stone weight is totalSum − 2 × dp[n][target].

Let's trace with stones = [2, 7, 4, 1, 8, 1]. Total sum = 23, target = 23 / 2 = 11.

Step 1: Initialize a 7×12 DP table. Row 0 (no stones) = all zeros. Column 0 (capacity 0) = all zeros.

Step 2: Row 1 (stone = 2): For capacity j ≥ 2, we can take this stone. dp[1][j] = 2 for all j ≥ 2. With just one stone of weight 2, we can achieve sum 2.

• Key cells: dp[1][2] = 2, dp[1][11] = 2

Step 3: Row 2 (stone = 7): Stone 7 opens new possibilities.

• dp[2][7] = max(2, 0+7) = 7 (take stone 7 alone)
• dp[2][9] = max(2, dp[1][2]+7) = max(2, 2+7) = 9 (take stones 2+7=9)
• dp[2][11] = max(2, dp[1][4]+7) = max(2, 2+7) = 9

Step 4: Row 3 (stone = 4): Combining with previous stones.

• dp[3][6] = max(2, dp[2][2]+4) = max(2, 2+4) = 6 (stones 2+4=6)
• dp[3][11] = max(9, dp[2][7]+4) = max(9, 7+4) = 11 — we hit the target! Stones {7,4} sum to exactly 11.

Step 5: Row 4 (stone = 1): Fills remaining gaps. dp[4][j] = j for all j from 0 to 11.

• Key: dp[4][3] = 3 (stones 2+1), dp[4][5] = 5 (stones 4+1), dp[4][8] = 8 (stones 7+1)

Step 6: Rows 5-6 (stones 8 and 1): No improvement beyond dp = [0,1,...,11]. The target sum of 11 was already achieved.

Step 7: Result: dp[6][11] = 11. Answer = 23 − 2×11 = 23 − 22 = 1.

The DP found that subset {7, 4} sums to 11 (or equivalently {2, 1, 8} sums to 11). The partition difference is |12 − 11| = 1.

1. Calculate totalSum = sum(stones) and target = totalSum / 2
2. Create a 2D table dp[n+1][target+1], initialized to 0
3. For each stone i from 1 to n:
   • For each capacity j from 0 to target:
     • Don't take stone: dp[i][j] = dp[i-1][j]
     • Take stone (if stones[i-1] ≤ j): dp[i][j] = max(dp[i][j], dp[i-1][j - stones[i-1]] + stones[i-1])
4. Return totalSum − 2 × dp[n][target]

Time Complexity: O(n × S/2)

Where n is the number of stones and S is the total sum. We fill a table of size n × (S/2) with O(1) work per cell. With n ≤ 30 and S ≤ 3000, the maximum number of operations is 30 × 1500 = 45,000 — extremely fast.

Space Complexity: O(n × S/2)

The full 2D DP table. For the worst case (30 stones, each 100), the table has 30 × 1500 = 45,000 entries — about 180 KB. Manageable, but we can do better.

We maintain a single 1D array dp[j] where dp[j] = the maximum sum achievable using a subset of the stones processed so far, with sum ≤ j.

For each new stone, we sweep the array right to left (from target down to stone):

• dp[j] = max(dp[j], dp[j - stone] + stone)

Why backwards? Because dp[j - stone] references a value from the previous stone's iteration. If we went left to right, dp[j - stone] might have already been updated in the current iteration, effectively using the same stone twice.

Think of it like packing a suitcase: for each item, you check from the fullest possible state down to the item's weight. This ensures each item is considered at most once.

After processing all stones, dp[target] gives the maximum subset sum ≤ S/2, and the answer is totalSum − 2 × dp[target].

Let's trace with stones = [2, 7, 4, 1, 8, 1]. Total = 23, target = 11.

Step 1: Initialize dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

Step 2: Stone = 2. Sweep j = 11 down to 2:

• Each dp[j] = max(dp[j], dp[j-2]+2). Since dp is all zeros, dp[j] becomes 2 for j ≥ 2.
• dp = [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Step 3: Stone = 7. Sweep j = 11 down to 7:

• dp[9] = max(2, dp[2]+7) = max(2, 9) = 9 (combo: 2+7=9)
• dp[7] = max(2, dp[0]+7) = max(2, 7) = 7 (stone 7 alone)
• dp = [0, 0, 2, 2, 2, 2, 2, 7, 7, 9, 9, 9]

Step 4: Stone = 4. Sweep j = 11 down to 4:

• dp[11] = max(9, dp[7]+4) = max(9, 7+4) = 11 — target reached!
• dp[6] = max(2, dp[2]+4) = max(2, 6) = 6 (combo: 2+4=6)
• dp = [0, 0, 2, 2, 4, 4, 6, 7, 7, 9, 9, 11]

Step 5: Stone = 1. Sweep j = 11 down to 1:

• Fills all remaining gaps: dp[10] = max(9, dp[9]+1) = 10, dp[8] = max(7, dp[7]+1) = 8, dp[5] = max(4, dp[4]+1) = 5, dp[3] = max(2, dp[2]+1) = 3, dp[1] = max(0, dp[0]+1) = 1.
• dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Step 6: Stones 8 and 1 (second): dp already has all values 0..11. No cell can be improved further — every achievable sum is already maximal.

Step 7: Result: dp[11] = 11. Answer = 23 − 2×11 = 1.

The backward iteration ensured each stone was used at most once. Only one array of 12 integers was needed instead of a 7×12 table.

1. Calculate totalSum = sum(stones) and target = totalSum / 2
2. Create a 1D array dp[target+1], initialized to 0
3. For each stone in the array:
   • Sweep j from target down to stone (backward!):
     • dp[j] = max(dp[j], dp[j - stone] + stone)
4. Return totalSum − 2 × dp[target]

Why backward? If we iterated forward (j = stone to target), when computing dp[j], the value dp[j - stone] might have already been updated in the current iteration — effectively using the same stone multiple times. Backward iteration ensures dp[j - stone] always reflects the state from the previous stone.

Time Complexity: O(n × S/2)

Same as the 2D approach. For each of n stones, we sweep through at most S/2 capacities. With n ≤ 30 and S ≤ 3000, at most 45,000 operations.

Space Complexity: O(S/2)

Only a single 1D array of size target+1 = S/2 + 1. For the worst case (total sum = 3000), this is just 1500 integers (~6 KB). Compared to the 2D table's 45,000 entries, this is a 30× space reduction.

Comparison of all three approaches: