Okay. Try this version.

1. It (finally) corrects the duplicates problem (with many thanks to betterworld++).
2. It will find the optimum solution much more often with far fewer iterations.

   In most tests I've run, a limit of 10* the number of elements finds the optimum even for large arrsys of widely spaced numbers.

   Most of my tests having been run using a custom shuffle that uses Math::Random::MT, but that was mostly to achieve repeatability. I see no reason that you will not see similar results using your native rand() and List::Util::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 ) {
#        printf "%6d : [@half] [@in] [@best]\n", abs( $soFar - $target
+ ) if $V;

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

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

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