Problem statement

https://leetcode.com/problems/last-stone-weight-ii/

Solution

We can reformulate the problem as follows: given values x1, x2, ..., xn put + or - sign between then such that we get the smallest absolute value. Notice that not every sum with + and - correspond to some process, for example if we have (9, 4, 3), we can not have 9 + 4 - 3. However for every such position we can look at if we stopped earlier at 9, (4 - 3) step. Then when we continue the process, we can only decrease value. So, for every position which can not be reached there exist smaller position we can reach, so it is safe to choose the smallest absolute value.

Complexity

It is O(M*n^2), where M = max(stones) and n = len(stones).

Code

class Solution:
    def lastStoneWeightII(self, stones):
        vals = set([0])
        for x in stones:
            vals2 = set([])
            for y in vals:
                vals2.add(y - x)
                vals2.add(y + x)
            vals = vals2
         
        return min(abs(x) for x in vals)

Remark

We can reformulate as we choose some subset of stones and make sum as close to sum(stones)/2 as possible.