laziness, impatience, and hubris PerlMonks

### Re: puzzle: how many ways to make \$100

by GrandFather (Sage)
 on Apr 29, 2006 at 00:44 UTC ( #546446=note: print w/replies, xml ) Need Help??

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

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

Create A New User
Node Status?
node history
Node Type: note [id://546446]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (9)
As of 2018-02-21 19:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (287 votes). Check out past polls.

Notices?