16. Last Stone Weight II

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 1:

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.

Solution: (DP)

Find two subset such that abs(S2 - S1) is minimum

s1 + s2 = sum dif = (s2 - s1) dif = (sum - 2 * s1) [Nee to minimize this value] assuming s1 <= sum/2 This problem is same as subset sum: Finding all possible sum formed and minimizing the difference.

class Solution
{
public:
    int lastStoneWeightII(vector<int> &stones)
    {

        int sum = 0;
        for (int i = 0; i < stones.size(); i++)
        {
            sum += stones[i];
        }

        int n = stones.size();

        vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));

        for (int i = 0; i <= n; i++)
        {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= sum; j++)
            {

                if (stones[i - 1] <= j)
                {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - stones[i - 1]];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        int s1 = sum / 2;
        int minDif = INT_MAX;

        for (int i = 0; i <= s1; i++)
        {
            if (dp[n][i])
            {
                int dif = sum - (2 * i);
                if (dif < minDif)
                {
                    minDif = dif;
                }
            }
        }

        return minDif;
    }
};

Time Complexity: O(n * m)