use strict;
use warnings;

my @all = (100, 50, 20, 10, 5);

use Memoize;

memoize('breakup');

my $count = 0;
sub nice
{
  my ($target, $sub) = @_;
  my @solns = breakup($target, $sub);
  foreach my $sol (@solns)
  {
    print join(", ", @$sol)."\n";
  }
}
nice(100, 0);
print "count = $count\n";

 
sub breakup
{
  my ($target, $sub) = @_;
  $count++;

  my $cur = $all[$sub];

  my @solns;
  if ($target == $cur)   
  {
    push(@solns, [$cur]);
  }
   
  if ($target >= $cur)
  {
    push(@solns, map {[$cur, @$_]} (breakup($target - $cur, $sub)));
  }

  push(@solns, breakup($target, $sub + 1)) unless ($sub == $#all);
 
  return @solns;
}