http://qs321.pair.com?node_id=546445

in reply to puzzle: how many ways to make \$100

You're looking for the Greedy Algorithm. It's basically the reverse from your approach: you start out with the highest denomination, then decrease that and spread the difference among the lower denominations.

I dug up my solution to problem 31 on Project Euler.

```#!/usr/bin/perl

use List::Util qw/ sum /;

@w     = ( 1, 2, 5, 10, 20, 50, 100 );
\$S     = 100;
\$found = 0;
@c     = ( 0, 0, 0, 0, 0, 0, 1 );

partition( \$S, @c );

print "\$/Total found: \$found\$/";

sub partition {
my ( \$s, @c ) = @_;

while(1) {
# exact change
\$found++ if \$s - amount( \@c, \@w ) == 0;

# last match
return if \$c[0] == \$s;

# decrement first non-zero
my \$i = 0;
\$i++ while \$c[\$i] == 0;
\$i == 0 ? \$c[0] = 0 : \$c[\$i]--;
@c[ 0 .. \$i - 1 ] = (0) x \$i;

# and redistribute difference
for my \$j ( reverse 0 .. \$i - 1 ) {
my \$Dj = \$s - amount( \@c, \@w );
\$c[\$j] = int( \$Dj / \$w[\$j] );
}
}
}

sub amount {
my ( \$x, \$y ) = @_;
return sum map { \$x->[\$_] * \$y->[\$_] } 0 .. \$#\$x;
}