Update: I know know why the problem didn't show up in my version of the script. As I mentioned, I'm using a custom shuffle routine, which does an in-place shuffle. The List::Util version of shuffle is not in-place, hence the last line of the for loop should be @in = shuffle @in; for use with List::Util, not shuffle @in; as for my version. I've update the code below.

I apologise. It is a legit bug. I'm amazed it hasn't shown up before and confused as to why it doesn't show up in my lightly modified version of the same script you posted, but...this fixes it. Till the next one....

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 ) {
#        printf "%6d : [@half] [@in] [@best]\n", abs( $soFar - $target
+ );

        $soFar += $in[ 0 ], push @half, shift @in
            while @in > 1 and $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 @half > 1 and $soFar > $target;
        return( \@half, \@in ) if $soFar == $target;

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

        srand( $_ );
        @in = shuffle @in;
        ## shuffle @in; ## Only works for an inplace shuffle!
    }
    my %seen; $seen{ $_ }++ for @best;
    return \@best, [ grep{ --$seen{ $_ } < 0 } @$aRef ];
}
[download]