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; } ##```## \$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 ```