Say I have an array of integers like so: [2,2,3,5,5,5,5,6,6,7,7,7,7,9,10]

I'd like to find all combinations of these values that when summed exceed the maximum (in this case 10) by the smallest amount (in this case a number that is closest to 11).

The function for this array would output [[9,2], [6,5], [7,2,2], ... etc]. If for example there is no possible combination that would make 11 it would try 12 and so on.

EDIT

This is not from an online course. I'm working on a hotel booking website. I have multiple rooms in the hotel, and I need to find all possible combinations for large groups. Imagine the array contains the amount of rooms by their capacity (2 x 2 beds, 1 x 3 beds, 5 x 5 beds etc...) and then I need to find all possible combinations of hotel rooms for eg. a conference of 37 people.

  • Welcome to Computer Science! Your question looks like interesting. If it comes from an online course or contest or article, please add a URL in the question. If it comes from a book or a paper, a reference. Besides paying proper attribute to the original source, all that information motivates and helps more people answer your question faster and better. (In case if you figured out this problem by yourself, please tell us a bit of background.) – Apass.Jack Oct 29 at 18:35
  • There is some ambiguity in the question. Instead of asking for clarification and back and forth, I will just wait to see if you can provide a url or reference. – Apass.Jack Oct 29 at 18:39
  • Your problem is probably very hard. The version in which you wish to know whether the minimal sum is at most X is probably NP-hard. – Yuval Filmus Oct 29 at 18:41
  • If the problem is actually a real world problem, then the number of different rooms is probably quite small, so being NP complete doesn't mean you cannot find the solution. – gnasher729 Oct 29 at 23:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.