# Last Stone Weight II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/last-stone-weight-ii)
Canonical: https://scaleengineer.com/dsa/problems/last-stone-weight-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an array of integers `stones` where `stones[i]` is the weight of the `ith` stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights `x` and `y` with `x <= y`. The result of this smash is:

* If `x == y`, both stones are destroyed, and
* If `x != y`, the stone of weight `x` is destroyed, and the stone of weight `y` has new weight `y - x`.

At the end of the game, there is **at most one** stone left.

Return _the smallest possible weight of the left stone_. If there are no stones left, return `0`.

**Example 1:**

**Input:** stones = [2,7,4,1,8,1]
**Output:** 1
**Explanation:**
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

**Example 2:**

**Input:** stones = [31,26,33,21,40]
**Output:** 5

**Constraints:**

* `1 <= stones.length <= 30`
* `1 <= stones[i] <= 100`

# Approaches
## Brute-force Recursion
This approach explores every possible way to partition the stones into two groups. For each stone, we can either place it in the first group or the second. This creates `2^n` possible partitions, where `n` is the number of stones. We can implement this using a recursive function that tries both possibilities for each stone and finds the minimum possible difference between the two groups' sums.
**Time:** O(2^n), where `n` is the number of stones. For each stone, we make two recursive calls, leading to an exponential number of computations. · **Space:** O(n), where `n` is the number of stones. This space is used by the recursion call stack.
**Pros:** Conceptually simple and straightforward to implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The problem of finding the minimum last stone weight can be rephrased as partitioning the set of stones into two subsets, `S1` and `S2`, such that the absolute difference of their sums, `|sum(S1) - sum(S2)|`, is minimized. This is because smashing two stones `x` and `y` to get `y - x` is equivalent to putting them in different groups. The brute-force approach systematically explores all `2^n` possible partitions. A recursive function can be designed to handle this exploration. For each stone, the function makes two recursive calls: one where the stone is added to `S1` and another where it's added to `S2`. The base case for the recursion is when all stones have been assigned, at which point we compute the difference and compare it with the minimum difference found so far.

```java
class Solution {
    public int lastStoneWeightII(int[] stones) {
        return findMinWeight(stones, 0, 0, 0);
    }

    private int findMinWeight(int[] stones, int index, int sum1, int sum2) {
        if (index == stones.length) {
            return Math.abs(sum1 - sum2);
        }

        // Option 1: Add the current stone to the first group
        int diff1 = findMinWeight(stones, index + 1, sum1 + stones[index], sum2);

        // Option 2: Add the current stone to the second group
        int diff2 = findMinWeight(stones, index + 1, sum1, sum2 + stones[index]);

        return Math.min(diff1, diff2);
    }
}
```
### Algorithm
1. The core idea is to simulate the smashing process by partitioning the stones into two groups. The final weight is the absolute difference between the total weights of these two groups.
2. We define a recursive function, for example, `findMinWeight(index, sum1, sum2)`.
3. `index`: The index of the current stone being considered.
4. `sum1`, `sum2`: The current total weights of the two groups.
5. **Base Case**: When `index` reaches the end of the `stones` array, all stones have been assigned to a group. We return the absolute difference `abs(sum1 - sum2)`.
6. **Recursive Step**: For the stone at `stones[index]`, we explore two possibilities:
   - Add `stones[index]` to the first group: Make a recursive call `findMinWeight(index + 1, sum1 + stones[index], sum2)`.
   - Add `stones[index]` to the second group: Make a recursive call `findMinWeight(index + 1, sum1, sum2 + stones[index])`.
7. The function returns the minimum of the results from these two recursive calls.
8. The initial call to start the process is `findMinWeight(0, 0, 0)`.

## Top-Down Dynamic Programming with Memoization
The brute-force approach suffers from re-computing solutions to the same subproblems. We can optimize this using memoization, a top-down dynamic programming technique. The problem can be transformed into finding a subset of stones whose sum is as close as possible to half of the total sum of all stones. This is a classic 0/1 Knapsack problem. We use a recursive function with a memoization table (e.g., a 2D array) to store the results of subproblems, defined by the current stone index and the remaining capacity (target sum).
**Time:** O(n * totalSum), where `n` is the number of stones. Each state `(index, capacity)` is computed only once. · **Space:** O(n * totalSum), where `n` is the number of stones. This is for the memoization table and the recursion stack.
**Pros:** Significantly more efficient than brute-force.; Guaranteed to find the optimal solution within the time limits for the given constraints.
**Cons:** The space complexity of O(n * totalSum) can be large if the total sum is very high, although it's acceptable for the given constraints.
### Explanation
By observing that the final weight is `|sum(S1) - sum(S2)|`, and `sum(S1) + sum(S2) = totalSum`, we can rewrite the expression to minimize as `totalSum - 2*sum(S1)`, assuming `sum(S1) <= sum(S2)`. To minimize this, we need to maximize `sum(S1)` such that `sum(S1) <= totalSum / 2`. This is the 0/1 Knapsack problem where item weights and values are the stone weights, and the knapsack capacity is `totalSum / 2`.
We define a function `findMaxSum(index, capacity)` that returns the maximum subset sum from stones up to `index` that fits within `capacity`. A 2D array `memo` stores the results to avoid redundant calculations.

```java
class Solution {
    private Integer[][] memo;

    public int lastStoneWeightII(int[] stones) {
        int totalSum = 0;
        for (int stone : stones) {
            totalSum += stone;
        }

        int target = totalSum / 2;
        memo = new Integer[stones.length][target + 1];
        
        int maxSum = findMaxSum(stones, stones.length - 1, target);
        
        return totalSum - 2 * maxSum;
    }

    private int findMaxSum(int[] stones, int index, int capacity) {
        if (index < 0 || capacity <= 0) {
            return 0;
        }

        if (memo[index][capacity] != null) {
            return memo[index][capacity];
        }

        // Option 1: Exclude the current stone
        int excludeSum = findMaxSum(stones, index - 1, capacity);

        // Option 2: Include the current stone if it fits
        int includeSum = 0;
        if (stones[index] <= capacity) {
            includeSum = stones[index] + findMaxSum(stones, index - 1, capacity - stones[index]);
        }

        memo[index][capacity] = Math.max(includeSum, excludeSum);
        return memo[index][capacity];
    }
}
```
### Algorithm
1. Reframe the problem: We want to partition the stones into two sets, `S1` and `S2`, to minimize `|sum(S1) - sum(S2)|`. Let `totalSum` be the sum of all stones. Then `sum(S2) = totalSum - sum(S1)`. We want to minimize `|sum(S1) - (totalSum - sum(S1))| = |2*sum(S1) - totalSum|`. This is minimized when `sum(S1)` is as close as possible to `totalSum / 2`.
2. The problem is now a 0/1 Knapsack problem: find a subset of stones whose sum is maximized but does not exceed `capacity = totalSum / 2`.
3. Define a recursive function `findMaxSum(index, capacity)` with memoization.
4. Create a memoization table `memo[n][capacity+1]` to store results of subproblems.
5. **Base Case**: If `index < 0` or `capacity <= 0`, return 0.
6. **Memoization Check**: If `memo[index][capacity]` is already computed, return the stored value.
7. **Recursive Step**: For `stones[index]`:
   - **Exclude option**: `findMaxSum(index - 1, capacity)`.
   - **Include option** (if `stones[index] <= capacity`): `stones[index] + findMaxSum(index - 1, capacity - stones[index])`.
8. The result for the current state is the maximum of the two options. Store it in the memo table.
9. The initial call is `findMaxSum(stones.length - 1, totalSum / 2)` to get `maxSum`.
10. The final answer is `totalSum - 2 * maxSum`.

## Bottom-Up Dynamic Programming (Most Efficient)
This is an iterative, bottom-up version of the dynamic programming solution. It solves the same 0/1 Knapsack problem but builds the solution from the ground up, which is often more efficient in practice and can be optimized for space. We use a boolean array to keep track of all possible subset sums that can be formed using the stones.
**Time:** O(n * totalSum). We have a nested loop iterating through `n` stones and sums up to `target` (`totalSum / 2`). · **Space:** O(totalSum). We only need a 1D array of size `target + 1` to store the reachable sums.
**Pros:** Optimal time complexity for this problem's constraints.; Most space-efficient DP solution, using only O(totalSum) space.; Iterative approach avoids recursion overhead, potentially leading to faster execution.
**Cons:** The logic, especially the backward iteration for the sum, might be less intuitive at first glance compared to the recursive formulation.
### Explanation
The bottom-up DP approach iteratively determines all achievable subset sums. We use a boolean array `dp` where `dp[i]` indicates whether a subset sum of `i` is possible. The size of this array is `(totalSum / 2) + 1`. We initialize `dp[0]` to `true`. Then, for each stone, we iterate through the possible sums from `target` down to the stone's weight. This backward iteration ensures that each stone is considered only once for each sum calculation. After filling the `dp` table, we find the largest sum `s` for which `dp[s]` is true. This `s` is the sum of one partition that is closest to `totalSum / 2`. The minimum difference is then `totalSum - 2*s`.

```java
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalSum = 0;
        for (int stone : stones) {
            totalSum += stone;
        }

        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }

        int maxSum = 0;
        for (int j = target; j >= 0; j--) {
            if (dp[j]) {
                maxSum = j;
                break;
            }
        }

        return totalSum - 2 * maxSum;
    }
}
```
### Algorithm
1. As with the memoization approach, transform the problem into finding the maximum subset sum `S` that is less than or equal to `totalSum / 2`.
2. Calculate `totalSum` of all stones and set `target = totalSum / 2`.
3. Create a 1D boolean array `dp` of size `target + 1`. `dp[j]` will be `true` if a subset with sum `j` is achievable.
4. Initialize `dp[0] = true`, as a sum of 0 is always possible (by choosing no stones).
5. Iterate through each `stone` in the `stones` array:
   - For each stone, update the `dp` array. Iterate from `j = target` down to `stone`.
   - Set `dp[j] = dp[j] || dp[j - stone]`. This update rule means a sum `j` is now possible if it was already possible before considering the current stone, or if a sum `j - stone` was possible (to which we now add the current `stone`). The backward iteration is crucial to prevent using the same stone multiple times in one subset.
6. After processing all stones, find the largest index `maxSum` from `target` down to 0 for which `dp[maxSum]` is `true`.
7. The final result is `totalSum - 2 * maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int lastStoneWeightII(int[] stones) {
    int s = 0;
    for (int v : stones) {
      s += v;
    }
    int m = stones.length;
    int n = s >> 1;
    int[] dp = new int[n + 1];
    for (int v : stones) {
      for (int j = n; j >= v; --j) {
        dp[j] = Math.max(dp[j], dp[j - v] + v);
      }
    }
    return s - dp[n] * 2;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} stones * @return {number} */ var lastStoneWeightII =
  function (stones) {
    let s = 0;
    for (let v of stones) {
      s += v;
    }
    const n = s >> 1;
    let dp = new Array(n + 1).fill(0);
    for (let v of stones) {
      for (let j = n; j >= v; --j) {
        dp[j] = Math.max(dp[j], dp[j - v] + v);
      }
    }
    return s - dp[n] * 2;
  };

```

### Python

```python
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int: s = sum(stones) m, n = len(stones), s >> 1 dp = [0] * (n + 1) for v in stones: for j in range(n, v - 1, - 1): dp[j] = max(dp[j], dp[j - v] + v) return s - dp[- 1] * 2

```

### CPP

```cpp
class Solution {
public:
  int lastStoneWeightII(vector<int> &stones) {
    int s = accumulate(stones.begin(), stones.end(), 0);
    int n = s >> 1;
    vector<int> dp(n + 1);
    for (int &v : stones)
      for (int j = n; j >= v; --j)
        dp[j] = max(dp[j], dp[j - v] + v);
    return s - dp[n] * 2;
  }
};

```