#!/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
    }
}