Hi Friends! I've tried a lot to solve below problem but after trying for 3-4 hour, I tried to find some hint / solution online to build / correct my own thinking. We cannot use dynamic programming to solve this problem, this was my first impression because size of max capacity is too large. Then I thought this could be solved using searching after sorting array, but it appears that answer can also be a subsequence of weights taken which puts me on thinking how can I use two pointer / binary search. Can I please get some hint to solve this question? I'm getting strong impression that it can be solved with binary search. But what would be the monotonous function to use for binary search, this I'm unable to figure out. Any help would be deeply appreciated. Thanks!
Problem: Ollie is new to the gym and is figuring out the maximum weights she can lift. The maximum capacity of the barbell is given as maxCapacity. Each barbell plate has a weight, given by weights[i]. Now Ollie has to select as many plates as she can but the total weight of the selected plates should not exceed maxCapacity. What is the maximum weight of plates Ollie can add to the barbell? For example, given barbell plates of weights of 1, 3 and 5 lbs and a barbell of maximum capacity 7 lbs — the right plates to insert would be 1 and 5 lbs (1+5 = 6), thus making the right answer 6.
Constraints: 1 ≤ n ≤ 42 1 ≤ maxCapacity ≤ 10^9 1 ≤ weights[i] ≤ 10^9