# Leetcode 1049. Last Stone Weight II

[link](https://leetcode.com/problems/last-stone-weight-ii)

---

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

---

The code defines a class Solution with a method lastStoneWeightII that takes a list of integers called stones as its input and returns an integer.

stoneSum is calculated as the sum of all the elements in the stones list. This represents the total weight of all the stones.

target is calculated as half of stoneSum, rounded up using the ceil function. This is because we want to divide the stones into two subsets, and we are trying to minimize the difference between the weights of these two subsets.

dp is a dictionary used for memoization. It will store the results of subproblems to avoid redundant calculations in the recursive function.

The code defines a recursive function dfs(i, total) which takes two parameters:

i: The current index of the stone being considered in the stones list.
total: The current total weight of the stones in one of the subsets.
The base case of the recursion is as follows:

If total is greater than or equal to target, or if i has reached the end of the stones list, we return the absolute difference between total and (stoneSum - total). This represents the difference in weights between the two subsets.
Before making a recursive call, the code checks if (i, total) is already in the dp dictionary. If it is, we return the precomputed result to avoid redundant calculations.

The recursive step is where the magic happens. The code calculates the minimum of two recursive calls:

dfs(i + 1, total): This represents the case where the current stone is not included in the current subset.
dfs(i + 1, total + stones[i]): This represents the case where the current stone is included in the current subset.
The result of the minimum of these two recursive calls is stored in the dp dictionary for the current (i, total) pair.

Finally, the dfs function is called initially with i as 0 and total as 0 to start the recursion.

The function returns the result of the initial dfs call, which represents the minimum difference in weights between the two subsets.

#### Solution 1

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        stoneSum = sum(stones)
        target = ceil(stoneSum / 2)
        dp = {}
        
        def dfs(i, total):
            if total >= target or i == len(stones):
                return abs(total - (stoneSum - total))
            
            if (i, total) in dp:
                return dp[(i, total)]

            dp[(i, total)] = min(dfs(i + 1, total), dfs(i + 1, total + stones[i]))
            
            return dp[(i, total)]
        
        return dfs(0, 0)
        

O(T): O(n * total)
O(S): O(n)