Finding all subsets which have nearly the desired sum

[halley]

Someone else came to me with a 1D variant of this problem as a homework example. I wrote this recursive version in a few minutes. This finds all possible combinations for 1D; you could add a scoring mechanism to find the optimum choice. I'm sure it can be improved, but it's speedy enough and simple enough for homework.

#!/usr/bin/perl

# First line of DATA is desired total and the tolerance.

my $Finish = <DATA>;
my ($Wanted, $Tolerance) = ($Finish =~ /(-?\d+)\s+(\d+)/);

# Other lines of DATA are the available elements.

my @Items = (<DATA>); chomp @Items;

#---------------------------------------------------------------------
+-------

my $Stack = ();

sub build
{
    my $index = shift;
    my $total = shift;

    while ($index < @Items)
    {
        my $num = $Items[$index];
        push(@Stack, $num);

        if ($num + $total > ($Wanted+$Tolerance))
        {
            next;
        }
        elsif ($num + $total >= ($Wanted-$Tolerance) and
               $num + $total <= ($Wanted+$Tolerance))
        {
            print "( @Stack ) = ", $num+$total, "\n";
        }
        else
        {
            build($index+1, $num + $total);
        }
    }
    continue
    {
        pop(@Stack);
        $index++;
    }
}

#---------------------------------------------------------------------
+-------

build(0, 0);

__DATA__
30 5
-5
5
10
15
20
10
25
25