Solving “Last Stone Weight II” problem

The problem

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks 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 totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)
Example:

Input: [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.

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 100

Let’s make the problem feel simpler

If we have weights a, b, c, d and e, then the right answer might be :

i. smash a and b (getting new stone of weight, say, a-b and let’s call it x)
ii. smash c and d (getting new stone of weight, say, c-d and let’s call it y)
iii. smash x and e (getting new stone of weight, say, x-e and let’s call it z)
iv. and finally smash z and y to get the final stone of weight z-y

So the result is z-y = (x-e)-(c-d) = (a-b-e)-(c-d)=(a+d)-(b+c+e)

Or the answer might be

i. smash a and b (getting new stone of weight, say, a-b and let’s call it x)
ii. smash c with x(getting new stone of weight, say, x-c = a-b-c and name it y)
iii. smash y and d (getting new stone of weight, say, y-d = a-b-c-d and let’s call it z)
iv. and finally smash z and e to get the final stone of weight z-e = a-b-c-d-e

So the result is a-(b+c+d+e)

You can try with a few more ways to smash the hell out of them and finally see that if all comes down to finding to groups of the stones and the wight difference is the resulting wight.
So what we really have to do here is to find a way to divide the stones into two groups so that their weight difference is minimum.
Take your time and try to grasp till this.
Now that we have simplified the problem, let’s get to solving it.

Dividing an array of positive integers into two groups with minimum difference

I’ll take a dynamic programming (DP) approach to solving this. This is quite similar to the 0–1 knapsack problem.

Let’s call the array of integers A. We’ll take a 2D array of size (n+1)*(sum/2) where n is the number of integers and sum is the sum of these integers. Let’s call this array dp and the elements of this array will be boolean.
So dp[i][j] will be set to True if there is exists a sub-array between the1st and i-th number (not index) of element of A that has a sum of j. That is if A[:i+1](in python terms) has any sub-array that has a sum of j .

So we can say that dp[i][0] for all i is True because all the sub-arrays have a sub-array that has a sum of 0.
Also, dp[0][j] is False for j!=0 because an empty sub-array can not have any some other than 0.

Now, that we have the base of the dp solution, we can move onto filling the whole dp array up. We can see that if dp[i][j] is True , then dp[i+1][j] will also be True . Moreover if j >= A[i-1] and dp[i-1][j-A[i-1]] is True then dp[i][j] is also True .

If you understand until this, we can then have the pseudo-code

If n = 1 then return A[0]
sum = sum of all weights in A
dp = [(n+1)*sum/2]
for i = 0 to i = n
    dp[i][0] = True
    dp[0][i] = False
dp[0][0] = True
for i = 1 to i = n
    for j = 1 to i = (summ/2)+1
        dp[i][j] = dp[i-1][j]
        if j >= A[i-1]
            dp[i][j] = dp[i][j] or dp[i-1][j-A[i-1]]
        
j = summ//2
while j >= 0:
    if dp[n][j]
       break
j -= 1
return sum - j*2

This has a worst case time complexity of O(n*sum) and space complexity of O(n*sum) . The space complexity can be improved by using two array of size (n + 1)*(sum/2 + 1) . Leaving this to the reader.