An athlete is lifting weights. The maximum capacity of the barbell is maxCapacity. Each barbell plate has a weight, weight[i]. Determine the maximum weight of plates that can be added to the barbell without exceeding maxCapacity.

Example

weights = [7, 1, 5, 6, 2]

maxCapacity = 7

There are 3 ways to reach the maximum weight: {7}, {1, 6} and {2, 5}. Other combinations are either more or less than 7 combined weight. Return 7.

Constraints

1 ≤ n ≤ 42 1 ≤ maxCapacity ≤ 10^9 1 ≤ weights[i][ ]≤ 10^9

Solution for 1e6 or 10^6 constraints:

int weightCapacity(vector<int> &weights, int maxCapacity) {
    
        int n = weights.size();
        vector<bool> dp(maxCapacity+1, false);
        dp[0] = true;
        int maxW = 0;
        for(int i = 0; i < n; ++i)
        {
    
            for(int j = maxCapacity-weights[i]; j>=0; --j)
            {
    	// Traversal in reverse order , The new state does not interfere with the old state to be traversed 
                if(dp[j])// j  Weight status exists 
                {
    
                    dp[j+weights[i]] = true;
                    maxW = max(maxW, j+weights[i]);
                }
            }
        }
        return maxW;
    }

How can we use binary search here for the tighter constraints. I understand the monotonicity but how do we check whether such a subsequence exists in the array that sums up to the mid weight?