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
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.