Leetcode 1049: 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

Problem Analysis:

We can group the stones into two groups. We should find such two groups so the sum of a group subtracts the sum of another group, the result is minimum. Assume the sum of two group is sum_1, sum_2, we should make sum_1-sum_2 is minimum.

So we can iterate the stones, when iterate the ith stone, it’s weight is weight_i, if we put it in the first group, we add weight_i, or we put it in the second group, we substract weight_i.

During the iteration, we can ignore the same sum values to reduce the computations. After iterate all stones, we can get all possibilities of sum values. Then the minimum sum value is the answer.

Solution

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        unordered_set<int> current{0};
        for (const auto& item : stones) {
            unordered_set<int> tmp;
            for (const auto& item2: current) 
                tmp.insert({item2 - item, item2 + item});
            swap(current, tmp);
        }

        return abs(*min_element(begin(current), end(current), [](int left, int right) {
            return abs(left) < abs(right);
        }));
    }
};

Time complexity is O(n²)

Space complexity is O(n)