This looks like a simulation problem: smash stones in some 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 (the strategy that works for Last Stone Weight I) does not give the minimum result here.

Every smash subtracts one stone's weight from another. Tracing through any sequence of smashes, each stone's original weight ends up 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 the answer is the absolute value, 1.

So the problem reduces to partitioning the stones into two groups so 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 the 0/1 Knapsack problem with capacity totalSum / 2.

Key Constraints:

Intuition

Try every way to assign each stone a + or - sign. Each stone belongs to one of two groups, so there are 2^n assignments. For each one, compute the difference between the two group sums and track the minimum.

Recursion expresses this directly: at each stone, put it in group 1 or group 2, then recurse on the remaining stones.

Algorithm

Example Walkthrough

Input:

The total sum is 23, so minResult starts at 23. The recursion explores all 2^6 = 64 sign assignments, where currentSum accumulates the weights placed in group 2, and each leaf computes |23 - 2 * currentSum|. A few representative leaves:

No partition can do better, because 23 is odd and the closest a subset sum can get to 11.5 is 11 or 12, both giving a difference of 1. After all 64 leaves are visited, minResult is 1, which is returned.

Code

The brute force tries every partition, but many recursive paths reach the same (index, currentSum) state and recompute it. Dynamic programming removes that redundancy by tracking which subset sums are reachable rather than enumerating every path.

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

Example Walkthrough

Code

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

Intuition

Since dp[i][j] only depends on dp[i-1][j] and dp[i-1][j - stones[i-1]], the 2D table collapses into a single 1D array. The one constraint is to iterate j from right to left, from target down to stone. When dp[j] is updated, dp[j - stone] must still hold the value from before the current stone was processed, and right-to-left order guarantees that, because lower indices are visited after higher ones.

Iterating left to right would read dp[j - stone] after it had already been updated for the current stone, which lets a single stone contribute more than once. That is the unbounded knapsack recurrence. Right-to-left order keeps each stone usable at most once, preserving the 0/1 constraint.

Algorithm

Example Walkthrough

Code