BinarySearch 0853 Crush Numbers

Problem statement

https://binarysearch.com/problems/Crush-Numbers/

Solution

Equal to Leetcode 1049. Last Stone Weight II.

Complexity

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

Code

class Solution:
    def solve(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)