Here's a recursive routine that does the trick:
use strict;
use warnings;
my @values = (100, 50, 20, 10, 5, 2, 1);
my $total = 100;
my $count = 0;
my @results;
@values = map {[$_, 0]} @values; # Generate counters and init to 0
findSubSums ($total, 0);
print "$_\n" for @results;
print scalar @results, " combinations found\n";
sub findSubSums {
my ($remaining, $index) = @_;
return if $remaining <= 0;
my $value = $values[$index][0];
my $counter = \$values[$index][1];
if ($index == $#values) {
#Special case for last element
$$counter = int ($remaining / $value);
dumpResult ($index) if $value * $$counter == $remaining;
return;
}
while ($remaining >= $value * $$counter) {
dumpResult ($index), last if $value * $$counter == $remaining;
findSubSums ($remaining - $value * $$counter, $index + 1);
++$$counter;
}
$$counter = 0; # Reset counter
}
sub dumpResult {
my @denoms = grep {$values[$_][1]} (0..shift);
push @results, join ' ', map {"\$$values[$_][0] x $values[$_][1]"}
+ @denoms;
return;
}
Partial output
$1 x 100
$2 x 1 $1 x 98
$2 x 2 $1 x 96
$2 x 3 $1 x 94
...
$2 x 50
$5 x 1 $1 x 95
$5 x 1 $2 x 1 $1 x 93
$5 x 1 $2 x 2 $1 x 91
...
$5 x 19 $1 x 5
$5 x 19 $2 x 1 $1 x 3
$5 x 19 $2 x 2 $1 x 1
$5 x 20
$10 x 1 $1 x 90
$10 x 1 $2 x 1 $1 x 88
$10 x 1 $2 x 2 $1 x 86
...
$20 x 5
$50 x 1 $1 x 50
$50 x 1 $2 x 1 $1 x 48
$50 x 1 $2 x 2 $1 x 46
$50 x 1 $2 x 3 $1 x 44
$50 x 1 $2 x 4 $1 x 42
...
$50 x 1 $20 x 2 $5 x 2
$50 x 1 $20 x 2 $10 x 1
$50 x 2
$100 x 1
4563 combinations found
DWIM is Perl's answer to Gödel