Loading problem…
You are given an array of integers stones where stones[i] is the weight of the i-th 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; 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: Smashing stones is the same as splitting them into two groups and subtracting the sums. The groups {2,1,8} (sum 11) and {7,4,1} (sum 12) are as balanced as possible, so the final stone weighs 12 - 11 = 1.
Example 2
Input: stones = [31,26,33,21,40]
Output: 5
Explanation: The total is 151. The best split is {33,40} = 73 and {31,26,21} = 78. No subset sums to 74 or 75, so the smallest remaining weight is 78 - 73 = 5.
Example 3
Input: stones = [1,2]
Output: 1
Explanation: The only move is to smash 1 and 2, which leaves a stone of weight 1.
Assigning + and - signs to stones and minimizing |sum| is equivalent to splitting them into two groups whose sums are as close as possible. Find the largest achievable subset sum ≤ total/2.
Run checks all cases above. Submit evaluates all test cases.