1. #!/usr/bin/perl 
2. use strict;
3. use warnings;
4. # steve the gambler problem solution
5. # http://www.destraynor.com/serendipity/index.php?/archives/113-Steve-the-Gambler-Caught-by-the-IRS.html
6. #
7. # pretty naive, unoptimized, no-error checking implementation
8. #
9. # given     : list of values (@num array)
10. # required  : find $nnum values such that they add up to zero. 
11. #
12. # dmitry@river:~/workspace$ time ./irs.pl
13. # 1000
14. # Result: -50 -21 13 171 14 -42 -58 -65 38 
15. #
16. # real    0m0.023s
17. # user    0m0.016s
18. # sys     0m0.008s
19. 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);
20. my $nnum = 9;
21. my $tot = 0;
22. sub f
23. {
24.     # where we.re at in the array
25.     my $index = shift;
26.     # current list of possible values
27.     my $a_ref = shift;
28.     # stats, total number of iterations
29.     $tot++;
30.     unless ($tot % 1000)
31.     {
32.         print .$totn.;
33.     }
34.     # if the list of possible values is over the required length, might as well terminate.
35.     if (scalar(@$a_ref) > $nnum)
36.     {
37.         return $a_ref;
38.     }
39.     # keep looking for a solution until we hit the end of the array
40.     while ($index < scalar(@num))
41.     {
42.         # add the next possible element to the list of values
43.         push @$a_ref, $num[$index];
44.         # solve the sub problem
45.         f(++$index, $a_ref);
46.         # see whether we have a solution
47.         my $sum = 0;
48.         map { $sum += $_; } @$a_ref;
49.         if ($sum == 0 && scalar(@$a_ref) == $nnum)
50.         {
51.             return @$a_ref;
52.         }
53.         # nope, the last value we added in this frame will not get us where we need to go
54.         # so discard it.
55.         pop @$a_ref;
56.     }
57.     return @$a_ref;
58. }
59. my $ref = [];
60. f(0, $ref);
61. print .Result: @{$ref} n.;
62. View this file Here (Right Click and save As)