#! perl -slw
use strict;
use List::Util qw[ sum shuffle ];

sub partition {
    my( $limit, $aRef ) = @_;
    my @in = sort{ $a <=> $b } @$aRef;
    my $target = sum( @in ) >> 1;
    my( $best, @best ) = 9e99;
    my $soFar = 0;
    my @half;
    for( 1 .. $limit ) {
        #print "$soFar : [@half] [@in] [@best]"; <>;
        $soFar += $in[ 0 ], push @half, shift @in while $soFar < $target;
        return( \@half, \@in ) if $soFar == $target;

        my $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        $soFar -= $half[ 0 ], push @in, shift @half while $soFar > $target;
        return( \@half, \@in ) if $soFar == $target;

        $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        @in = shuffle @in;
    }
    my %seen; $seen{ $_ }++ for @best;
##    return \@best, [ grep !$seen{ $_ }--, @$aRef ]; ## Fix duplicates bug
    return \@best, [ grep{ !exists $seen{ $_ } or !$seen{ $_ }-- } @$aRef ];
}


for (
    [ 62, 83, 121, 281, 486, 734, 771, 854, 885, 1003 ],
    [ 7,10,12,15,40 ],
    [ 8, 14, 32, 29  ],
    [ 41, 37, 37, 43 ],
    [ 99, (1)x99  ],
    [ 1 .. 99 ],
    [ map $_*2+1, 1 .. 50 ],
    [ map int( rand 1000 ), 1 .. 100 ],
) {
    my( $a1, $a2 ) = partition( 1e2, $_ );
    my( $t1, $t2 ) = ( sum( @$a1), sum( @$a2 ) );
    print "\n@$a1 := ", $t1;
    print "@$a2 := ", $t2;
    print "Diff: ", abs( $t1 - $t2 );
}