# Fill the time slot with the best match

If I have the following array: pieces = {35,15,20,25,30,10} and the time slot is 80 minutes. How do I do the following:
1. Fill the time slot with any pieces for the perfect fit. (In our case: 30,35,15 or 15,25,30,10 etc.) 2. Fill the time slot with the best fit possible with deviation: (Let's say our time slot is 103 minutes and the deviation is +/-20 minutes. So, we are looking for the best fit anywhere in the 83-123 minute range.
3. Is there any optimizations that can be done if pieces array is sorted?

I'm looking for basic CS algorithms and strategies for optimizing runtime or space. I'm not looking for a specific solution to my problem. Instead, I'm interested in the CS topics I need to look into.

I'm able to solve the simplest version of this problem: Find out if 2 pieces for the time slot and return true. Solution: Loop through the array. Create hashtable and check if hashtable contains timeslot-pieces[i] if yes, then return true, if no, then add to hashtable.

• This is SUBSET SUM. – Yuval Filmus Oct 9 '18 at 0:43

This is a well known problem in computer science, and can be mentioned as "Find all distinct subset sums in an array". The obvious solution is to generate all subsets which will take O(2^n) time for an array of i elements. Instead, if the sum that you can make is relatively small, you can can use dynamic programming technique to precompute a table which will mark the reached sums. The implementation details of these two ideas can be seen here. Notice that this answers also the second question.