Pyth, 15 13
heJc2osNyQehJ
Input, output formats:
Input:
[1, 2, 3, 4, 5]
Output:
[3, 5]
[1, 2, 4]
heJc2osNyQehJ
Q = eval(input())
yQ Take all subsets of Q.
osN Order those element lists by their sums.
c2 Cut the list in half.
J Save it to J.
he Print the first element of the second half.
ehJ Print the last element of the first half.
This works because y
returns the subsets in such an order that each subset and its complement are equidistant fom the center. Since the sum of a subset and the sum of its complement will always be equidistant from the center, the list after osNyQ
will also have this property. Thus, the center two elements of osNyQ
are complements, and must have an optimal split.
If it's only necessary to output the bags carried in one of the two hands, the following code is sufficient:
hec2osNyQ