Take the following array of integers:

[60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30]

They need to be sorted into pairs of sub-arrays. The first sub-array in each pair must total at most 180, and the second must total at most 240.

How would you find the right combinations of elements so that no elements are remaining after all pairs have been created? I'm told that it is possible with this data set.

  • 2
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Aug 31 '14 at 7:12
  • $\begingroup$ Are you looking for one solution, or a general method to solve this kind of problem? $\endgroup$ – Florian F Aug 31 '14 at 21:26
  • $\begingroup$ There must be a typo. An array of 180 plus an array of 240 sums to 420. The sum of your items is 785, not a multiple of 420. And all elements are multiple of 15, except for the 5 which is not. You can not use it in a subarray that sums to 180 or 240. $\endgroup$ – Florian F Aug 31 '14 at 21:35
  • 1
    $\begingroup$ I have integrated your edit into the actual question, since future visitors will not care about the previous wrong version. $\endgroup$ – FrankW Sep 1 '14 at 7:21
  • 1
    $\begingroup$ This problem does indeed seem to admit trivial solutions if there are not too many big elements, and none at all otherwise. Are there no other restrictions, such as minimising the number of pairs in the result? $\endgroup$ – Raphael Sep 1 '14 at 10:58

This is trivial: Since all elements are less than 90, you can create one sub-array with 2 elements and 17 sub-arrays with a single element each and pair them in any way you like.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.