AlgoMaster Logo

Last Stone Weight II

Last Updated: March 28, 2026

medium
5 min read

Understanding the Problem

At first glance, this looks like a simulation problem: just smash stones in some clever order and find the minimum leftover. But "any two stones" on each turn means the number of possible orderings is enormous, and greedily picking the two heaviest (like in Last Stone Weight I) does not guarantee the minimum result here.

The key insight is to think about what smashing really means. Every stone ends up either added or subtracted in the final result. If you trace through any sequence of smashes, you will find that each stone's weight is either added with a + sign or a - sign in the final expression. For example, with stones [2, 7, 4, 1, 8, 1], one valid sequence produces (+8) + (-7) + (-4) + (+2) + (-1) + (+1) = -1, and we take the absolute value to get 1.

So the problem reduces to: partition the stones into two groups such that the difference between the group sums is minimized. If group 1 sums to S1 and group 2 sums to S2 with S1 >= S2, the answer is S1 - S2. Since S1 + S2 = totalSum, we want S2 to be as close to totalSum / 2 as possible. This is exactly the classic 0/1 Knapsack problem where the capacity is totalSum / 2.

Key Constraints:

  • 1 <= stones.length <= 30 -- With n up to 30, O(2^n) brute force means about 10^9 operations, which is too slow. But O(n sum) DP with sum up to 30 100 = 3000 is very fast.
  • 1 <= stones[i] <= 100 -- The maximum total sum is 30 100 = 3000, so the DP table size is at most 30 1500 = 45,000 cells. This is tiny.

Approach 1: Brute Force (Recursion)

Intuition

The most direct approach is to try all possible ways to assign each stone a + or - sign. Since each stone belongs to one of two groups, we have 2^n possible assignments. For each assignment, compute the difference and track the minimum.

We can implement this with recursion: at each stone, we either add it to group 1 or group 2, then recurse on the remaining stones.

Algorithm

  1. Compute the total sum of all stones.
  2. Use a recursive function that processes one stone at a time.
  3. At each stone, try two choices: include it in the "subtract" group (add to current sum) or exclude it (skip to the next stone).
  4. When all stones are processed, the result is totalSum - 2 * currentSum. Track the minimum absolute result across all recursive calls.

Example Walkthrough

Input:

0
2
1
7
2
4
3
1
4
8
5
1
stones

We try all 2^6 = 64 possible sign assignments. One of them assigns + to {2, 8, 1} and - to {7, 4, 1}, giving (2+8+1) - (7+4+1) = 11 - 12 = -1. The absolute value is 1, which turns out to be the minimum across all assignments.

Code

The brute force tries every possible partition, but many recursive paths reach the same (index, currentSum) state. What if we used dynamic programming to avoid recomputing overlapping subproblems?

Approach 2: Dynamic Programming (2D)

Intuition

Since the problem reduces to "find a subset with sum as close to totalSum / 2 as possible," we can use a 2D DP table. Define dp[i][j] as whether it is possible to achieve a subset sum of exactly j using the first i stones. For each stone, we either include it in the subset or not. After filling the table, we scan for the largest j <= totalSum / 2 where dp[n][j] is true, and the answer is totalSum - 2 * j.

This is the standard 0/1 Knapsack formulation. The "capacity" is totalSum / 2, and each stone's weight equals its value. We are trying to fill the knapsack as full as possible.

Algorithm

  1. Compute totalSum and set target = totalSum / 2.
  2. Create a 2D boolean array dp[n+1][target+1]. Set dp[0][0] = true (zero stones, zero sum is achievable).
  3. For each stone i from 1 to n:
    • For each sum j from 0 to target:
      • dp[i][j] = dp[i-1][j] (skip this stone)
      • If j >= stones[i-1], also check dp[i][j] |= dp[i-1][j - stones[i-1]] (include this stone)
  4. Find the largest j where dp[n][j] is true.
  5. Return totalSum - 2 * j.

Example Walkthrough

1Initial: only sum 0 is achievable
0
true
1
false
2
false
3
false
4
false
5
false
6
false
7
false
8
false
9
false
10
false
11
false
1/7

Code

The 2D DP works, but each row only depends on the previous row. We can compress it to a single 1D array.

Approach 3: Dynamic Programming (1D Space-Optimized)

Intuition

Since dp[i][j] only depends on dp[i-1][j] and dp[i-1][j - stones[i-1]], we can collapse the 2D table into a 1D array. The trick is to iterate j from right to left (from target down to stones[i]). This ensures that when we update dp[j], the value at dp[j - stones[i]] still reflects the previous row (it has not been overwritten yet in this iteration).

If you iterate left to right, you would use the already-updated values from the current row, effectively allowing a stone to be used multiple times. That would be the unbounded knapsack, which is not what we want. Right-to-left iteration preserves the 0/1 constraint: each stone is used at most once.

Algorithm

  1. Compute totalSum and set target = totalSum / 2.
  2. Create a 1D boolean array dp[target+1]. Set dp[0] = true.
  3. For each stone:
    • Iterate j from target down to stone (right to left).
    • Set dp[j] = dp[j] || dp[j - stone].
  4. Find the largest j where dp[j] is true.
  5. Return totalSum - 2 * j.

Example Walkthrough

1dp[0]=true (empty subset has sum 0)
0
true
1
false
2
false
3
false
4
false
5
false
6
false
7
false
8
false
9
false
10
false
11
false
1/8

Code