# LeetCode 1049: Last Stone Weight II

## Problem Restatement

We have a collection of stones with integer weights.

In each step, we take two stones and smash them together. If their weights are `x` and `y` with `x <= y`, we get a stone of weight `y - x`.

We need to return the smallest possible weight of the remaining stone (or 0 if none remain).

The official constraints state that `1 <= stones.length <= 30` and `1 <= stones[i] <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `stones` |
| Output | Minimum possible final stone weight |

Function shape:

```python
def lastStoneWeightII(stones: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
stones = [2, 7, 4, 1, 8, 1]
```

`sum = 23`. We can achieve a minimum weight of `1`.

Answer:

```python
1
```

## Key Insight

The smashing process is equivalent to assigning `+` or `-` signs to each stone weight and taking the absolute value of the sum.

We want to partition the stones into two groups S1 and S2 to minimize `|S1 - S2|`.

This is a 0/1 knapsack problem: find the largest achievable sum ≤ `total // 2`.

The answer is `total - 2 * best_sum`.

## Algorithm

1. Compute `total = sum(stones)`.
2. DP: find all achievable sums up to `total // 2`.
3. Find the largest achievable sum ≤ `total // 2`.
4. Return `total - 2 * best`.

## Correctness

Every partition into two groups corresponds to a subset sum. Minimizing `|S1 - S2|` is equivalent to finding a subset summing to as close to `total / 2` as possible.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * S)` | DP table where S = total sum / 2 |
| Space | `O(S)` | Rolling DP array |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def lastStoneWeightII(self, stones: list[int]) -> int:
        total = sum(stones)
        target = total // 2
        dp = {0}

        for stone in stones:
            dp = {s + stone for s in dp} | dp
            dp = {s for s in dp if s <= target}

        best = max(dp)
        return total - 2 * best
```

## Code Explanation

We maintain the set of all achievable sums up to `target`:

```python
dp = {s + stone for s in dp} | dp
```

Adding each stone creates new achievable sums. We keep only those ≤ `target`.

The answer is:

```python
return total - 2 * best
```

Where `best` is the largest achievable partial sum.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.lastStoneWeightII([2, 7, 4, 1, 8, 1]) == 1
    assert s.lastStoneWeightII([31, 26, 33, 21, 40]) == 5
    assert s.lastStoneWeightII([1, 2]) == 1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `1` | Near-equal partition |
| 5 stones | `5` | Optimal partition minimizes difference |
| Two stones | `1` | `|2 - 1| = 1` |