Pathologically Eclectic Rubbish Lister PerlMonks

### Comment on

 Need Help??

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

In reply to Re: puzzle: how many ways to make \$100 by GrandFather
in thread puzzle: how many ways to make \$100 by davidj

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (4)
As of 2018-03-22 08:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (273 votes). Check out past polls.

Notices?