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