Re: Divide an array into 2 subsets to verify their sum is equal or not.

[hdb]

Using recursion:

use strict;
use warnings;
use List::Util qw/sum/;

# finds one solution
sub findsum {
        my ($target, @array) = @_;
        while( @array ) {
                my $cand = shift @array;
                return () if $cand > $target;
                return ( $cand ) if $cand==$target;
                my @sol = findsum( $target-$cand, @array );
                return ($cand, @sol) if @sol;
        }
        return ();
}

my @array = qw(1 3 5 7);
my $total = sum(@array);

die "Odd total $total cannot be split!\n" if $total % 2;

my @sol = findsum( $total/2, sort @array );
if( @sol ) {
        print "Solution: ",join( ",", @sol), "\n";
} else {
        print "No solution.";
}