100 = 50 + 10 + 10 + 10 + 10 + 10

##</code><code>##

100 = 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10

##</code><code>##

100
50, 50
50, 20, 20, 10
50, 20, 20, 5, 5
50, 20, 10, 10, 10
50, 20, 10, 10, 5, 5
50, 20, 10, 5, 5, 5, 5
50, 20, 5, 5, 5, 5, 5, 5
50, 10, 10, 10, 10, 10
50, 10, 10, 10, 10, 5, 5
50, 10, 10, 10, 5, 5, 5, 5
50, 10, 10, 5, 5, 5, 5, 5, 5
50, 10, 5, 5, 5, 5, 5, 5, 5, 5
50, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 20, 20, 20
20, 20, 20, 20, 10, 10
20, 20, 20, 20, 10, 5, 5
20, 20, 20, 20, 5, 5, 5, 5
20, 20, 20, 10, 10, 10, 10
20, 20, 20, 10, 10, 10, 5, 5
20, 20, 20, 10, 10, 5, 5, 5, 5
20, 20, 20, 10, 5, 5, 5, 5, 5, 5
20, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 10, 10, 10, 10, 10, 10
20, 20, 10, 10, 10, 10, 10, 5, 5
20, 20, 10, 10, 10, 10, 5, 5, 5, 5
20, 20, 10, 10, 10, 5, 5, 5, 5, 5, 5
20, 20, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 10, 10, 10, 10, 10, 10, 10
20, 10, 10, 10, 10, 10, 10, 10, 5, 5
20, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5
20, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5
20, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 10, 10, 10, 10, 10, 10
10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 5
10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5
10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
count = 46


##</code><code>##

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;
}