<p>You are given an array of integers <code>stones</code> where <code>stones[i]</code> is the weight of the <code>i<sup>th</sup></code> stone.</p>

<p>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 <code>x</code> and <code>y</code> with <code>x &lt;= y</code>. The result of this smash is:</p>

<ul>
	<li>If <code>x == y</code>, both stones are destroyed, and</li>
	<li>If <code>x != y</code>, the stone of weight <code>x</code> is destroyed, and the stone of weight <code>y</code> has new weight <code>y - x</code>.</li>
</ul>

<p>At the end of the game, there is <strong>at most one</strong> stone left.</p>

<p>Return <em>the smallest possible weight of the left stone</em>. If there are no stones left, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stones = [2,7,4,1,8,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong>
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&#39;s the optimal value.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stones = [31,26,33,21,40]
<strong>Output:</strong> 5
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= stones.length &lt;= 30</code></li>
	<li><code>1 &lt;= stones[i] &lt;= 100</code></li>
</ul>

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones)
    {
        
        int ans = INT_MAX;
        
        unordered_set<int> st;
        
        st.insert(0); // for single element in stones
        
        for(auto &x: stones)
        {
            
            auto t = st;
            
            st.clear();
            
            for(auto &num: t)
            {
                st.insert(x-num);
                
                st.insert(x+num);
            }
        }
        
        for(auto &x: st)
        {
            ans = min(ans,abs(x));
        }
        
        return ans;
        
        /*For each num, two new elements are inserted into st. The first one is the difference between num and n, and the second one is the sum of num and n. This covers all possible differences between accumulated weights after smashing stones.*/
        
        //O(n^2),O(1)
    }
};
/*
Inserting 0 into the set at the beginning serves as a base case for the subsequent calculations.

When calculating the difference and sum with x for each element in the set st, having 0 in the set ensures that it covers the possibility where one stone is subtracted from another stone of the same weight.

For example, consider the scenario where the input vector stones contains only one stone. If we didn't have 0 in the set initially, the algorithm wouldn't consider the case where the stone is smashed with itself, resulting in a weight of 0.

By inserting 0 at the beginning, we ensure that all possible differences between accumulated weights after smashing stones are covered, including the case where a stone is smashed with itself, resulting in a weight of 0.*/
20187