#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{sum};

my @test_arrays = ( 
    [1, 3, 8, 4], 
    [1, 6, 2], 
    [1, 3, 5, 7], 
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
);  

check_arrays($_) for @test_arrays;

sub check_arrays {
    my @full_array = @{shift()};
    print "Checking: (", join(", " => @full_array), ")";
    my $sum = sum @full_array;

    if ($sum % 2) {
        print "\tSubsets not equal";
        return;
    }   

    my $half = $sum / 2;
    my (@a1, @a2);

    for (sort { $b <=> $a } @full_array) {
        push @{(sum(@a1) || 0) + $_ <= $half ? \@a1 : \@a2} => $_;
    }

    print "\tSubsets: (", join(", " => sort { $a <=> $b } @a1),
            ") and (", join(", " => sort { $a <=> $b } @a2), ")";
    print "\tSubset sum = $half";
}

##</code><code>##

$ pm_split_equal_sums.pl
Checking: (1, 3, 8, 4)
	Subsets: (8) and (1, 3, 4)
	Subset sum = 8
Checking: (1, 6, 2)
	Subsets not equal
Checking: (1, 3, 5, 7)
	Subsets: (1, 7) and (3, 5)
	Subset sum = 8
Checking: (4, 3, 2, 2, 1)
	Subsets: (2, 4) and (1, 2, 3)
	Subset sum = 6
Checking: (4, 3, 2, 2, 2, 2, 1)
	Subsets: (1, 3, 4) and (2, 2, 2, 2)
	Subset sum = 8
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
	Subsets: (1, 2, 8, 9) and (4, 5, 5, 6)
	Subset sum = 20

##</code><code>##

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{sum};
use Test::More;

my @test_equal_subsets = (
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
);

my @test_unequal_subsets = (
    [1, 6, 2],
    [7, 5, 3, 3],
    [8, 4, 4, 7, 6, 3],
    [0, 1],
    [1, 2],
    [1],
    [2],
);

plan tests => scalar @test_equal_subsets + scalar @test_unequal_subsets;

for (@test_equal_subsets) {
    is(check_arrays($_), 1, 'Expecting equal subsets.');
}

for (@test_unequal_subsets) {
    is(check_arrays($_), 0, 'Not expecting equal subsets.');
}

sub check_arrays {
    my $full_array = shift;

    print "Checking: (", join(", " => @$full_array), ")";

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", join(", " => @$full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) { 
        print "\tSubsets not equal.";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my (@a1, @a2);
    my $a1_total = 0;

    for (sort { $b <=> $a } @$full_array) {
        if ($a1_total + $_ <= $half_sum) {
            push @a1, $_;
            $a1_total += $_;
        }
        else {
            push @a2, $_;
        }
    }

    if ($a1_total == $half_sum) {
        print "\tSubsets: (", join(", " => sort { $a <=> $b } @a1),
                ") and (", join(", " => sort { $a <=> $b } @a2), ")";
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal.";
        return 0
    }
}

##</code><code>##

$ prove pm_split_equal_sums.pl
pm_split_equal_sums.pl .. ok     
All tests successful.
Files=1, Tests=19,  0 wallclock secs ( 0.03 usr  0.01 sys +  0.02 cusr  0.00 csys =  0.06 CPU)
Result: PASS

##</code><code>##

$ pm_split_equal_sums.pl
1..19
Checking: (1, 3, 8, 4)
	Subsets: (8) and (1, 3, 4)
	Subset sum = 8
ok 1 - Expecting equal subsets.
Checking: (1, 3, 5, 7)
	Subsets: (1, 7) and (3, 5)
	Subset sum = 8
ok 2 - Expecting equal subsets.
Checking: (4, 3, 2, 2, 1)
	Subsets: (2, 4) and (1, 2, 3)
	Subset sum = 6
ok 3 - Expecting equal subsets.
Checking: (4, 3, 2, 2, 2, 2, 1)
	Subsets: (1, 3, 4) and (2, 2, 2, 2)
	Subset sum = 8
ok 4 - Expecting equal subsets.
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
	Subsets: (1, 2, 8, 9) and (4, 5, 5, 6)
	Subset sum = 20
ok 5 - Expecting equal subsets.
Checking: (1, 1)
	Subsets: (1) and (1)
	Subset sum = 1
ok 6 - Expecting equal subsets.
Checking: (2, 2)
	Subsets: (2) and (2)
	Subset sum = 2
ok 7 - Expecting equal subsets.
Checking: ()
	Subsets: () and ()
	Subset sum = 0
ok 8 - Expecting equal subsets.
Checking: (0)
	Subsets: (0) and ()
	Subset sum = 0
ok 9 - Expecting equal subsets.
Checking: (0, 0)
	Subsets: (0, 0) and ()
	Subset sum = 0
ok 10 - Expecting equal subsets.
Checking: (0, 0, 0)
	Subsets: (0, 0, 0) and ()
	Subset sum = 0
ok 11 - Expecting equal subsets.
Checking: (0, 0, 0, 0)
	Subsets: (0, 0, 0, 0) and ()
	Subset sum = 0
ok 12 - Expecting equal subsets.
Checking: (1, 6, 2)
	Subsets not equal.
ok 13 - Not expecting equal subsets.
Checking: (7, 5, 3, 3)
	Subsets not equal.
ok 14 - Not expecting equal subsets.
Checking: (8, 4, 4, 7, 6, 3)
	Subsets not equal.
ok 15 - Not expecting equal subsets.
Checking: (0, 1)
	Subsets not equal.
ok 16 - Not expecting equal subsets.
Checking: (1, 2)
	Subsets not equal.
ok 17 - Not expecting equal subsets.
Checking: (1)
	Subsets not equal.
ok 18 - Not expecting equal subsets.
Checking: (2)
	Subsets not equal.
ok 19 - Not expecting equal subsets.

##</code><code>##

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{sum};
use Test::More;
use Time::HiRes qw[ time ];
use Getopt::Long;

my %opt = (
    test_more   => 1,
    time_hires  => 1,
    volume_tests        => 0,
    volume_power_max    => 3,
    array_limit => 3,
);

GetOptions(map {
    join('|' => @{[join '' => /(?>^|_)([a-z])/gi]}, $_) . ':i' => \$opt{$_}
} keys %opt);

my $test_equal_subsets = [
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [8, 4, 4, 7, 6, 3],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
];

my $test_unequal_subsets = [
    [1, 6, 2],
    [7, 5, 3, 3],
    [1, 2 ,3, 7],
    [0, 1],
    [1, 2],
    [1],
    [2],
    [8, 1, 2, 3],
];

if ($opt{volume_tests}) {
    for (1 .. $opt{volume_power_max}) {
        my @volume = (1 .. 10**$_ / 2) x 2;
        push @$test_equal_subsets, [@volume];
        push @volume, 10**(2 * $_);
        push @$test_unequal_subsets, [@volume];
    }
}

if ($opt{test_more}) {
    plan tests => scalar @$test_equal_subsets + scalar @$test_unequal_subsets;
}

my @expectations = ('Not expecting equal subsets.', 'Expecting equal subsets.');
my @subsets_data = ([$test_unequal_subsets, 0, 0], [$test_equal_subsets, 1, 1]);

for (@subsets_data) {
    my ($subsets, $expect_code, $expect_name_index) = @$_;
    my $expect_name = $expectations[$expect_name_index];

    for (@$subsets) {
        my $start = time if $opt{time_hires};

        if ($opt{test_more}) {
            is(check_arrays($_), $expect_code, $expect_name);
        }
        else {
            check_arrays($_);
        }

        printf "Took %f seconds\n", time() - $start if $opt{time_hires};
    }
}

sub check_arrays {
    my $full_array = shift;

    print 'Checking: (', array_string($full_array), ')';

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", array_string($full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) {
        print "\tSubsets not equal.";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my @sorted_array = sort { $b <=> $a } @$full_array;

    if ($sorted_array[0] > $half_sum) {
        print "\tSubsets not equal.";
        return 0;
    }

    my (@a1, @a2);
    my $total = 0;

    while (@sorted_array) {
        $total = 0;
        for (@sorted_array) {
            if ($total + $_ <= $half_sum) {
                push @a1, $_;
                $total += $_;
            }
        }

        if ($total == $half_sum) {
            push @a2, @sorted_array;
            last;
        }
        else {
            push @a2, shift @sorted_array or last;
            $total = 0;
        }
    }

    if ($total == $half_sum) {
        print "\tSubsets: (", array_string([sort { $a <=> $b } @a2]), ')';
        print "\t     and (", array_string([sort { $a <=> $b } @a2]), ')';
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal.";
        return 0
    }
}

sub array_string {
    my $array = shift;

    return join(', ' => @$array > 3 * $opt{array_limit}
        ? ( @$array[0 .. $opt{array_limit} - 1],
            " ... [snip: @{[@$array - 2 * $opt{array_limit}]} elements] ...",
            @$array[@$array - $opt{array_limit} .. $#$array] )
        : @$array);
}

##</code><code>##

$ pm_split_equal_sums.pl --tm=1 --th=1 --vt=1 --vpm=5 --al=3
1..31
Checking: (1, 6, 2)
	Subsets not equal.
ok 1 - Not expecting equal subsets.
Took 0.000307 seconds
Checking: (7, 5, 3, 3)
	Subsets not equal.
ok 2 - Not expecting equal subsets.
Took 0.000197 seconds
Checking: (1, 2, 3, 7)
	Subsets not equal.
ok 3 - Not expecting equal subsets.
Took 0.000180 seconds
Checking: (0, 1)
	Subsets not equal.
ok 4 - Not expecting equal subsets.
Took 0.000166 seconds
Checking: (1, 2)
	Subsets not equal.
ok 5 - Not expecting equal subsets.
Took 0.000165 seconds
Checking: (1)
	Subsets not equal.
ok 6 - Not expecting equal subsets.
Took 0.000164 seconds
Checking: (2)
	Subsets not equal.
ok 7 - Not expecting equal subsets.
Took 0.000168 seconds
Checking: (8, 1, 2, 3)
	Subsets not equal.
ok 8 - Not expecting equal subsets.
Took 0.000170 seconds
Checking: (1, 2, 3,  ... [snip: 5 elements] ..., 4, 5, 100)
	Subsets not equal.
ok 9 - Not expecting equal subsets.
Took 0.000183 seconds
Checking: (1, 2, 3,  ... [snip: 95 elements] ..., 49, 50, 10000)
	Subsets not equal.
ok 10 - Not expecting equal subsets.
Took 0.000191 seconds
Checking: (1, 2, 3,  ... [snip: 995 elements] ..., 499, 500, 1000000)
	Subsets not equal.
ok 11 - Not expecting equal subsets.
Took 0.000313 seconds
Checking: (1, 2, 3,  ... [snip: 9995 elements] ..., 4999, 5000, 100000000)
	Subsets not equal.
ok 12 - Not expecting equal subsets.
Took 0.001494 seconds
Checking: (1, 2, 3,  ... [snip: 99995 elements] ..., 49999, 50000, 10000000000)
	Subsets not equal.
ok 13 - Not expecting equal subsets.
Took 0.013494 seconds
Checking: (1, 3, 8, 4)
	Subsets: (1, 3, 4, 8)
	     and (1, 3, 4, 8)
	Subset sum = 8
ok 14 - Expecting equal subsets.
Took 0.000205 seconds
Checking: (1, 3, 5, 7)
	Subsets: (1, 3, 5, 7)
	     and (1, 3, 5, 7)
	Subset sum = 8
ok 15 - Expecting equal subsets.
Took 0.000195 seconds
Checking: (4, 3, 2, 2, 1)
	Subsets: (1, 2, 2, 3, 4)
	     and (1, 2, 2, 3, 4)
	Subset sum = 6
ok 16 - Expecting equal subsets.
Took 0.000205 seconds
Checking: (4, 3, 2, 2, 2, 2, 1)
	Subsets: (1, 2, 2, 2, 2, 3, 4)
	     and (1, 2, 2, 2, 2, 3, 4)
	Subset sum = 8
ok 17 - Expecting equal subsets.
Took 0.000201 seconds
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
	Subsets: (1, 2, 4, 5, 5, 6, 8, 9)
	     and (1, 2, 4, 5, 5, 6, 8, 9)
	Subset sum = 20
ok 18 - Expecting equal subsets.
Took 0.000202 seconds
Checking: (8, 4, 4, 7, 6, 3)
	Subsets: (3, 4, 4, 6, 7, 8)
	     and (3, 4, 4, 6, 7, 8)
	Subset sum = 16
ok 19 - Expecting equal subsets.
Took 0.000199 seconds
Checking: (1, 1)
	Subsets: (1, 1)
	     and (1, 1)
	Subset sum = 1
ok 20 - Expecting equal subsets.
Took 0.000188 seconds
Checking: (2, 2)
	Subsets: (2, 2)
	     and (2, 2)
	Subset sum = 2
ok 21 - Expecting equal subsets.
Took 0.000186 seconds
Checking: ()
	Subsets: () and ()
	Subset sum = 0
ok 22 - Expecting equal subsets.
Took 0.000167 seconds
Checking: (0)
	Subsets: (0) and ()
	Subset sum = 0
ok 23 - Expecting equal subsets.
Took 0.000166 seconds
Checking: (0, 0)
	Subsets: (0, 0) and ()
	Subset sum = 0
ok 24 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0, 0)
	Subsets: (0, 0, 0) and ()
	Subset sum = 0
ok 25 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0, 0, 0)
	Subsets: (0, 0, 0, 0) and ()
	Subset sum = 0
ok 26 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (1, 2, 3,  ... [snip: 4 elements] ..., 3, 4, 5)
	Subsets: (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
	     and (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
	Subset sum = 15
ok 27 - Expecting equal subsets.
Took 0.000211 seconds
Checking: (1, 2, 3,  ... [snip: 94 elements] ..., 48, 49, 50)
	Subsets: (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
	     and (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
	Subset sum = 1275
ok 28 - Expecting equal subsets.
Took 0.000269 seconds
Checking: (1, 2, 3,  ... [snip: 994 elements] ..., 498, 499, 500)
	Subsets: (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
	     and (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
	Subset sum = 125250
ok 29 - Expecting equal subsets.
Took 0.000762 seconds
Checking: (1, 2, 3,  ... [snip: 9994 elements] ..., 4998, 4999, 5000)
	Subsets: (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 5000)
	     and (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 5000)
	Subset sum = 12502500
ok 30 - Expecting equal subsets.
Took 0.005873 seconds
Checking: (1, 2, 3,  ... [snip: 99994 elements] ..., 49998, 49999, 50000)
	Subsets: (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 50000)
	     and (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 50000)
	Subset sum = 1250025000
ok 31 - Expecting equal subsets.
Took 0.060788 seconds

##</code><code>##

$ pm_split_equal_sums.pl --tm=0 --th=1 --vt=1 --vpm=5 --al=3
Checking: (1, 6, 2)
	Subsets not equal.
Took 0.000059 seconds
Checking: (7, 5, 3, 3)
	Subsets not equal.
Took 0.000036 seconds
Checking: (1, 2, 3, 7)
	Subsets not equal.
Took 0.000010 seconds
Checking: (0, 1)
	Subsets not equal.
Took 0.000009 seconds
Checking: (1, 2)
	Subsets not equal.
Took 0.000008 seconds
Checking: (1)
	Subsets not equal.
Took 0.000008 seconds
Checking: (2)
	Subsets not equal.
Took 0.000011 seconds
Checking: (8, 1, 2, 3)
	Subsets not equal.
Took 0.000012 seconds
Checking: (1, 2, 3,  ... [snip: 5 elements] ..., 4, 5, 100)
	Subsets not equal.
Took 0.000026 seconds
Checking: (1, 2, 3,  ... [snip: 95 elements] ..., 49, 50, 10000)
	Subsets not equal.
Took 0.000031 seconds
Checking: (1, 2, 3,  ... [snip: 995 elements] ..., 499, 500, 1000000)
	Subsets not equal.
Took 0.000150 seconds
Checking: (1, 2, 3,  ... [snip: 9995 elements] ..., 4999, 5000, 100000000)
	Subsets not equal.
Took 0.001309 seconds
Checking: (1, 2, 3,  ... [snip: 99995 elements] ..., 49999, 50000, 10000000000)
	Subsets not equal.
Took 0.012939 seconds
Checking: (1, 3, 8, 4)
	Subsets: (1, 3, 4, 8)
	     and (1, 3, 4, 8)
	Subset sum = 8
Took 0.000054 seconds
Checking: (1, 3, 5, 7)
	Subsets: (1, 3, 5, 7)
	     and (1, 3, 5, 7)
	Subset sum = 8
Took 0.000029 seconds
Checking: (4, 3, 2, 2, 1)
	Subsets: (1, 2, 2, 3, 4)
	     and (1, 2, 2, 3, 4)
	Subset sum = 6
Took 0.000032 seconds
Checking: (4, 3, 2, 2, 2, 2, 1)
	Subsets: (1, 2, 2, 2, 2, 3, 4)
	     and (1, 2, 2, 2, 2, 3, 4)
	Subset sum = 8
Took 0.000035 seconds
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
	Subsets: (1, 2, 4, 5, 5, 6, 8, 9)
	     and (1, 2, 4, 5, 5, 6, 8, 9)
	Subset sum = 20
Took 0.000038 seconds
Checking: (8, 4, 4, 7, 6, 3)
	Subsets: (3, 4, 4, 6, 7, 8)
	     and (3, 4, 4, 6, 7, 8)
	Subset sum = 16
Took 0.000036 seconds
Checking: (1, 1)
	Subsets: (1, 1)
	     and (1, 1)
	Subset sum = 1
Took 0.000024 seconds
Checking: (2, 2)
	Subsets: (2, 2)
	     and (2, 2)
	Subset sum = 2
Took 0.000025 seconds
Checking: ()
	Subsets: () and ()
	Subset sum = 0
Took 0.000011 seconds
Checking: (0)
	Subsets: (0) and ()
	Subset sum = 0
Took 0.000011 seconds
Checking: (0, 0)
	Subsets: (0, 0) and ()
	Subset sum = 0
Took 0.000011 seconds
Checking: (0, 0, 0)
	Subsets: (0, 0, 0) and ()
	Subset sum = 0
Took 0.000011 seconds
Checking: (0, 0, 0, 0)
	Subsets: (0, 0, 0, 0) and ()
	Subset sum = 0
Took 0.000011 seconds
Checking: (1, 2, 3,  ... [snip: 4 elements] ..., 3, 4, 5)
	Subsets: (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
	     and (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
	Subset sum = 15
Took 0.000050 seconds
Checking: (1, 2, 3,  ... [snip: 94 elements] ..., 48, 49, 50)
	Subsets: (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
	     and (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
	Subset sum = 1275
Took 0.000111 seconds
Checking: (1, 2, 3,  ... [snip: 994 elements] ..., 498, 499, 500)
	Subsets: (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
	     and (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
	Subset sum = 125250
Took 0.000599 seconds
Checking: (1, 2, 3,  ... [snip: 9994 elements] ..., 4998, 4999, 5000)
	Subsets: (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 5000)
	     and (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 5000)
	Subset sum = 12502500
Took 0.005701 seconds
Checking: (1, 2, 3,  ... [snip: 99994 elements] ..., 49998, 49999, 50000)
	Subsets: (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 50000)
	     and (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 50000)
	Subset sum = 1250025000
Took 0.060971 seconds

##</code><code>##

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{first sum};
use Test::More;
use Time::HiRes qw{time};
use Getopt::Long;

my %opt = (
    test_more   => 1,
    time_hires  => 1,
    volume_tests        => 0,
    volume_power_max    => 3,
    array_limit => 3,
);

GetOptions(map {
    join('|' => @{[join '' => /(?>^|_)([a-z])/gi]}, $_) . ':i' => \$opt{$_}
} keys %opt);

my $test_equal_subsets = [
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [8, 4, 4, 7, 6, 3],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
    [ (1) x 100 ],
    [ 1 .. 1000 ],
];

my $test_unequal_subsets = [
    [1, 6, 2],
    [7, 5, 3, 3],
    [1, 2 ,3, 7],
    [0, 1],
    [1, 2],
    [1],
    [2],
    [8, 1, 2, 3],
    [ 1 .. 10 ],
    [ 1 .. 100 ],
];

if ($opt{volume_tests}) {
    for (1 .. $opt{volume_power_max}) {
        my @volume = map { (($_), ($_)) } 1 .. 8**$_ / 2;
        push @$test_equal_subsets, [@volume];
        push @$test_unequal_subsets, [@volume, 8**(2 * $_)];
    }
}

if ($opt{test_more}) {
    plan tests => scalar @$test_equal_subsets + scalar @$test_unequal_subsets;
}

my @expectations = ('Not expecting equal subsets.', 'Expecting equal subsets.');
my @subsets_data = ([$test_unequal_subsets, 0, 0], [$test_equal_subsets, 1, 1]);

for (@subsets_data) {
    my ($subsets, $expect_code, $expect_name_index) = @$_;
    my $expect_name = $expectations[$expect_name_index];

    for (@$subsets) {
        my $start = time if $opt{time_hires};

        if ($opt{test_more}) {
            is(check_arrays($_), $expect_code, $expect_name);
        }
        else {
            check_arrays($_);
        }

        printf "Took %f seconds\n", time() - $start if $opt{time_hires};
    }
}

sub check_arrays {
    my $full_array = shift;

    print 'Checking: (', array_string($full_array), ')';

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", array_string($full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) {
        print "\tSubsets not equal: sum of starting array is odd ($full_sum).";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my @sorted_array = sort { $b % 2 <=> $a % 2 || $b <=> $a } @$full_array;

    if (my $big = first { $_ > $half_sum } @sorted_array) {
        print "\tSubsets not equal: element ($big) larger than sum of rest.";
        return 0;
    }

    my (@a1, @a2);
    my $total = 0;

    while (@sorted_array) {
        push @a1, shift @sorted_array;
        $total += $a1[$#a1];

        @sorted_array = map { $total + $_ <= $half_sum
            ? do { push @a1, $_; $total += $_; () } : $_
        } @sorted_array;

        if ($total == $half_sum) {
            (@a2, @sorted_array) = (@a2, @sorted_array);
        }
        else {
            push @a2, pop @a1 if @a1;
        }
    }

    if ($total == $half_sum) {
        print "\tSubsets: (", array_string([sort { $a <=> $b } @a1]), ')';
        print "\t     and (", array_string([sort { $a <=> $b } @a2]), ')';
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal: no solution found.";
        return 0
    }
}

sub array_string {
    my $array = shift;

    return join(', ' => @$array > 3 * $opt{array_limit}
        ? ( @$array[0 .. $opt{array_limit} - 1],
            " ... [snip: @{[@$array - 2 * $opt{array_limit}]} elements] ...",
            @$array[@$array - $opt{array_limit} .. $#$array] )
        : @$array);
}

##</code><code>##

$ pm_split_equal_sums.pl --tm=1 --th=1 --vt=1 --vpm=8 --al=3
1..41
Checking: (1, 6, 2)
	Subsets not equal: sum of starting array is odd (9).
ok 1 - Not expecting equal subsets.
Took 0.000318 seconds
Checking: (7, 5, 3, 3)
	Subsets not equal: no solution found.
ok 2 - Not expecting equal subsets.
Took 0.000233 seconds
Checking: (1, 2, 3, 7)
	Subsets not equal: sum of starting array is odd (13).
ok 3 - Not expecting equal subsets.
Took 0.000169 seconds
Checking: (0, 1)
	Subsets not equal: sum of starting array is odd (1).
ok 4 - Not expecting equal subsets.
Took 0.000165 seconds
Checking: (1, 2)
	Subsets not equal: sum of starting array is odd (3).
ok 5 - Not expecting equal subsets.
Took 0.000167 seconds
Checking: (1)
	Subsets not equal: sum of starting array is odd (1).
ok 6 - Not expecting equal subsets.
Took 0.000165 seconds
Checking: (2)
	Subsets not equal: element (2) larger than sum of rest.
ok 7 - Not expecting equal subsets.
Took 0.000177 seconds
Checking: (8, 1, 2, 3)
	Subsets not equal: element (8) larger than sum of rest.
ok 8 - Not expecting equal subsets.
Took 0.000179 seconds
Checking: (1, 2, 3,  ... [snip: 4 elements] ..., 8, 9, 10)
	Subsets not equal: sum of starting array is odd (55).
ok 9 - Not expecting equal subsets.
Took 0.000179 seconds
Checking: (1, 2, 3,  ... [snip: 94 elements] ..., 98, 99, 100)
	Subsets not equal: no solution found.
ok 10 - Not expecting equal subsets.
Took 0.000817 seconds
Checking: (1, 1, 2, 2, 3, 3, 4, 4, 64)
	Subsets not equal: element (64) larger than sum of rest.
ok 11 - Not expecting equal subsets.
Took 0.000193 seconds
Checking: (1, 1, 2,  ... [snip: 59 elements] ..., 32, 32, 4096)
	Subsets not equal: element (4096) larger than sum of rest.
ok 12 - Not expecting equal subsets.
Took 0.000379 seconds
Checking: (1, 1, 2,  ... [snip: 507 elements] ..., 256, 256, 262144)
	Subsets not equal: element (262144) larger than sum of rest.
ok 13 - Not expecting equal subsets.
Took 0.000769 seconds
Checking: (1, 1, 2,  ... [snip: 4091 elements] ..., 2048, 2048, 16777216)
	Subsets not equal: element (16777216) larger than sum of rest.
ok 14 - Not expecting equal subsets.
Took 0.004773 seconds
Checking: (1, 1, 2,  ... [snip: 32763 elements] ..., 16384, 16384, 1073741824)
	Subsets not equal: element (1073741824) larger than sum of rest.
ok 15 - Not expecting equal subsets.
Took 0.035878 seconds
Checking: (1, 1, 2,  ... [snip: 262139 elements] ..., 131072, 131072, 68719476736)
	Subsets not equal: element (68719476736) larger than sum of rest.
ok 16 - Not expecting equal subsets.
Took 0.294454 seconds
Checking: (1, 1, 2,  ... [snip: 2097147 elements] ..., 1048576, 1048576, 4398046511104)
	Subsets not equal: element (4398046511104) larger than sum of rest.
ok 17 - Not expecting equal subsets.
Took 2.395664 seconds
Checking: (1, 1, 2,  ... [snip: 16777211 elements] ..., 8388608, 8388608, 281474976710656)
	Subsets not equal: element (281474976710656) larger than sum of rest.
ok 18 - Not expecting equal subsets.
Took 19.422507 seconds
Checking: (1, 3, 8, 4)
	Subsets: (1, 3, 4)
	     and (8)
	Subset sum = 8
ok 19 - Expecting equal subsets.
Took 0.000223 seconds
Checking: (1, 3, 5, 7)
	Subsets: (1, 7)
	     and (3, 5)
	Subset sum = 8
ok 20 - Expecting equal subsets.
Took 0.000201 seconds
Checking: (4, 3, 2, 2, 1)
	Subsets: (1, 2, 3)
	     and (2, 4)
	Subset sum = 6
ok 21 - Expecting equal subsets.
Took 0.000203 seconds
Checking: (4, 3, 2, 2, 2, 2, 1)
	Subsets: (1, 3, 4)
	     and (2, 2, 2, 2)
	Subset sum = 8
ok 22 - Expecting equal subsets.
Took 0.000208 seconds
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
	Subsets: (1, 5, 5, 9)
	     and (2, 4, 6, 8)
	Subset sum = 20
ok 23 - Expecting equal subsets.
Took 0.000209 seconds
Checking: (8, 4, 4, 7, 6, 3)
	Subsets: (3, 6, 7)
	     and (4, 4, 8)
	Subset sum = 16
ok 24 - Expecting equal subsets.
Took 0.000206 seconds
Checking: (1, 1)
	Subsets: (1)
	     and (1)
	Subset sum = 1
ok 25 - Expecting equal subsets.
Took 0.000197 seconds
Checking: (2, 2)
	Subsets: (2)
	     and (2)
	Subset sum = 2
ok 26 - Expecting equal subsets.
Took 0.000195 seconds
Checking: ()
	Subsets: () and ()
	Subset sum = 0
ok 27 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0)
	Subsets: (0) and ()
	Subset sum = 0
ok 28 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0)
	Subsets: (0, 0) and ()
	Subset sum = 0
ok 29 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0, 0)
	Subsets: (0, 0, 0) and ()
	Subset sum = 0
ok 30 - Expecting equal subsets.
Took 0.000170 seconds
Checking: (0, 0, 0, 0)
	Subsets: (0, 0, 0, 0) and ()
	Subset sum = 0
ok 31 - Expecting equal subsets.
Took 0.000181 seconds
Checking: (1, 1, 1,  ... [snip: 94 elements] ..., 1, 1, 1)
	Subsets: (1, 1, 1,  ... [snip: 44 elements] ..., 1, 1, 1)
	     and (1, 1, 1,  ... [snip: 44 elements] ..., 1, 1, 1)
	Subset sum = 50
ok 32 - Expecting equal subsets.
Took 0.000323 seconds
Checking: (1, 2, 3,  ... [snip: 994 elements] ..., 998, 999, 1000)
	Subsets: (1, 3, 5,  ... [snip: 495 elements] ..., 995, 997, 999)
	     and (2, 4, 6,  ... [snip: 493 elements] ..., 996, 998, 1000)
	Subset sum = 250250
ok 33 - Expecting equal subsets.
Took 0.001866 seconds
Checking: (1, 1, 2, 2, 3, 3, 4, 4)
	Subsets: (1, 1, 2, 3, 3)
	     and (2, 4, 4)
	Subset sum = 10
ok 34 - Expecting equal subsets.
Took 0.000212 seconds
Checking: (1, 1, 2,  ... [snip: 58 elements] ..., 31, 32, 32)
	Subsets: (1, 1, 3,  ... [snip: 27 elements] ..., 29, 31, 31)
	     and (2, 2, 4,  ... [snip: 25 elements] ..., 30, 32, 32)
	Subset sum = 528
ok 35 - Expecting equal subsets.
Took 0.000310 seconds
Checking: (1, 1, 2,  ... [snip: 506 elements] ..., 255, 256, 256)
	Subsets: (1, 1, 3,  ... [snip: 251 elements] ..., 253, 255, 255)
	     and (2, 2, 4,  ... [snip: 249 elements] ..., 254, 256, 256)
	Subset sum = 32896
ok 36 - Expecting equal subsets.
Took 0.001029 seconds
Checking: (1, 1, 2,  ... [snip: 4090 elements] ..., 2047, 2048, 2048)
	Subsets: (1, 1, 3,  ... [snip: 2043 elements] ..., 2045, 2047, 2047)
	     and (2, 2, 4,  ... [snip: 2041 elements] ..., 2046, 2048, 2048)
	Subset sum = 2098176
ok 37 - Expecting equal subsets.
Took 0.006883 seconds
Checking: (1, 1, 2,  ... [snip: 32762 elements] ..., 16383, 16384, 16384)
	Subsets: (1, 1, 3,  ... [snip: 16379 elements] ..., 16381, 16383, 16383)
	     and (2, 2, 4,  ... [snip: 16377 elements] ..., 16382, 16384, 16384)
	Subset sum = 134225920
ok 38 - Expecting equal subsets.
Took 0.054265 seconds
Checking: (1, 1, 2,  ... [snip: 262138 elements] ..., 131071, 131072, 131072)
	Subsets: (1, 1, 3,  ... [snip: 131067 elements] ..., 131069, 131071, 131071)
	     and (2, 2, 4,  ... [snip: 131065 elements] ..., 131070, 131072, 131072)
	Subset sum = 8590000128
ok 39 - Expecting equal subsets.
Took 0.449057 seconds
Checking: (1, 1, 2,  ... [snip: 2097146 elements] ..., 1048575, 1048576, 1048576)
	Subsets: (1, 1, 3,  ... [snip: 1048571 elements] ..., 1048573, 1048575, 1048575)
	     and (2, 2, 4,  ... [snip: 1048569 elements] ..., 1048574, 1048576, 1048576)
	Subset sum = 549756338176
ok 40 - Expecting equal subsets.
Took 3.644046 seconds
Checking: (1, 1, 2,  ... [snip: 16777210 elements] ..., 8388607, 8388608, 8388608)
	Subsets: (1, 1, 3,  ... [snip: 8388603 elements] ..., 8388605, 8388607, 8388607)
	     and (2, 2, 4,  ... [snip: 8388601 elements] ..., 8388606, 8388608, 8388608)
	Subset sum = 35184376283136
ok 41 - Expecting equal subsets.
Took 89.489836 seconds