class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int sumA = sum / 2; 
        vector<bool> dp(sumA + 1, 0);

        dp[0] = 1;
        for (int& stone : stones) {
            for (int j = sumA; j >= stone; j--) {
                dp[j] = dp[j] | dp[j - stone];
            }
        }
       
        while (sumA) {
            if (dp[sumA])
                break;
            sumA--;
        }
        return sum - 2*sumA;
    }
};