# Distributing values of an array into smaller arrays with bounded sums

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.

• What did you try? Where did you get stuck? – David Richerby Aug 31 '14 at 7:12
• Are you looking for one solution, or a general method to solve this kind of problem? – Florian F Aug 31 '14 at 21:26
• 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. – Florian F Aug 31 '14 at 21:35
• I have integrated your edit into the actual question, since future visitors will not care about the previous wrong version. – FrankW Sep 1 '14 at 7:21
• 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? – Raphael Sep 1 '14 at 10:58