#!/usr/bin/perl 
use strict;
use warnings;

# steve the gambler problem solution

# http://www.destraynor.com/serendipity/index.php?/archives/113-Steve-the-Gambler-Caught-by-the-IRS.html
#
# pretty naive, unoptimized, no-error checking implementation
#
# given     : list of values (@num array)
# required  : find $nnum values such that they add up to zero. 
#
# dmitry@river:~/workspace$ time ./irs.pl
# 1000

# Result: -50 -21 13 171 14 -42 -58 -65 38 
#
# real    0m0.023s
# user    0m0.016s
# sys     0m0.008s

my @num = (-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101, 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8);

my $nnum = 9;
my $tot = 0;

sub f
{
    # where we.re at in the array
    my $index = shift;

    # current list of possible values
    my $a_ref = shift;

    # stats, total number of iterations

    $tot++;
    unless ($tot % 1000)
    {

        print .$totn.;
    }

    # if the list of possible values is over the required length, might as well terminate.
    if (scalar(@$a_ref) > $nnum)

    {
        return $a_ref;
    }

    # keep looking for a solution until we hit the end of the array
    while ($index < scalar(@num))

    {
        # add the next possible element to the list of values
        push @$a_ref, $num[$index];

        # solve the sub problem
        f(++$index, $a_ref);

        # see whether we have a solution

        my $sum = 0;
        map { $sum += $_; } @$a_ref;

        if ($sum == 0 && scalar(@$a_ref) == $nnum)

        {
            return @$a_ref;
        }

        # nope, the last value we added in this frame will not get us where we need to go

        # so discard it.
        pop @$a_ref;
    }

    return @$a_ref;

}

my $ref = [];

f(0, $ref);

print .Result: @{$ref} n.;