in reply to Divide an array into 2 subsets to verify their sum is equal or not.
choroba's Exploreallpossiblecombinations mechanism works okay for smallish sets (max:32 or 64 depending upon your Perl), but will get very slow for anything much larger than 20 or so.
This will very quickly (less than 0.001 of a second) find a solution, if one exists, for sets of 100s or 1000s of elements. : #! perl slw
use strict;
use Time::HiRes qw[ time ];
use List::Util qw[ sum ];
sub partition {
my $sum = sum @_;
return if $sum & 1;
$sum /= 2;
my @s = sort{ $b <=> $a } @_;
my @a;
my( $t, $n ) = ( 0, 1 );
$t + $s[$n] <= $sum and $t+= $s[$n] and push @a, $n while ++$n < @
+s and $t <= $sum;
@a = delete @s[ @a ];
@s = grep defined, @s;
return unless sum( @a ) == sum( @s );
return \@a, \@s;
}
our $N //= 64;
my( $a, $b ) = partition 1,3,5,7;
print "sum( @{ $a } ) == sum( @{ $b } )" if $a;
my @set = map int( rand 100 ), 1 .. $N;
my $start = time;
( $a, $b ) = partition @set;
printf "Took %f seconds\n", time()  $start;
if( $a ) {
printf "(%u) == sum( @{ $a } ) == sum( @{ $b } )\n", sum @$a;
}
else {
print "No solution existed for the $N element set @set";
}
A few runs: C:\test>1031699 N=1e1
sum( 7 1 ) == sum( 5 3 )
Took 0.000042 seconds
No solution existed for the 1e1 elemet set 19 41 38 74 95 79 28 90 86
+87
C:\test>1031699 N=1e1
sum( 7 1 ) == sum( 5 3 )
Took 0.000093 seconds
(184) == sum( 99 53 28 2 2 ) == sum( 91 48 24 11 10 )
C:\test>1031699 N=1e2
sum( 7 1 ) == sum( 5 3 )
Took 0.000186 seconds
(2418) == sum( 99 98 97 97 96 95 95 93 90 89 88 88 84 84 82 82 82 81 8
+0 79 75 74 73 73 73 72 71 69 59 ) == sum( 67 67 66 65 64 62 61 60 58
+57 57 55 55 51 51 51 49 49 47 47 45 44 42 42 41 41 40 38 38 37 36 35
+34 34 34 33 33 32 31 31 29 28 28 27 27 27 26 26 24 24 23 23 21 20 20
+16 16 15 14 13 13 12 12 11 10 8 7 6 5 5 2 )
C:\test>1031699 N=1e3
sum( 7 1 ) == sum( 5 3 )
Took 0.001379 seconds
(25172) == sum( 99 99 99 99 ... 71 71 71 70 70 70 33 0 0 0 ) == sum(
+70 70 70 70 70 70 ... 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 )
C:\test>1031699 N=1e3
sum( 7 1 ) == sum( 5 3 )
Took 0.000053 seconds
No solution existed for the 1e3 elemet set 26 ... 93 10 10
C:\test>1031699 N=1e4
sum( 7 1 ) == sum( 5 3 )
Took 0.013463 seconds
(247975) == sum( 99 99 ... 0 0 0 0 0 0 0 0 0 ) == sum( 70 70 ... 1 1 1
+ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 )
C:\test>1031699 N=1e4
sum( 7 1 ) == sum( 5 3 )
Took 0.000238 seconds
No solution existed for the 1e4 elemet set 60 ...72 43 21 61 24 16
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Divide an array into 2 subsets to verify their sum is equal or not. by choroba (Chancellor) on May 02, 2013 at 10:52 UTC 
It gives a wrong answer for 2, 12, 4
 [reply] [d/l] 

Corrected. Thanks.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
 [reply] 
