Given a collection of integers and threshold value T, divide the collection into as many groups as possible whose sum >= T.
The remaining integers (whose sum < T, so another group cannot be formed) should be left outside of the groups.
Constraints:
- length of the list <= 1,000
- values and T <= 1,000,000
Is there an algorithm for this problem in polynomial time?
For example given [25,25,25,50,50,50,10] and a threshold T = 70 it should return:
[25,50]
[25,50]
[25,50]
Remaining: [10]
Selecting [25,25,25] as one of the groups would make it possible to only form one more group, [50,50] and the remaining values would be [50,10]. Two groups are not the optimal amount of groups, which is why this solution would be incorrect.
