Skip to main content
3 of 7
deleted 567 characters in body
isaacg
  • 42.1k
  • 5
  • 73
  • 213

Pyth, 15 13

heJc2osNyQehJ

Input, output formats:

Input:
[1, 2, 3, 4, 5]
Output:
[3, 5]
[1, 2, 4]

Demonstration.

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
isaacg
  • 42.1k
  • 5
  • 73
  • 213