use Memoize;
memoize 'restricted_partitions';
sub restricted_partitions {
my ($N, @coins) = @_;
## can't do it if $N is negative (might get called with $N<0 if
## we have coins bigger than $N)
## only one way to make change for 0
return 0 if $N < 0;
return 1 if $N == 0;
## pick any available coin to be the coin with the lowest ID in this
## partition. once we pick that, we have left to partition $N-$coin,
## and can't use coins with lower IDs to do it...
my $total = 0;
for (0 .. $#coins) {
$total += restricted_partitions($N-$coins[$_], @coins[$_ .. $#coins]);
}
return $total;
}
print restricted_partitions(@ARGV), $/;