#! /usr/bin/perl -w

use strict;

my @parts = (100, 50, 20, 10, 5, 1);

sub partitions { my $n = shift; return partmax($n, $n) };

sub partmax {
        my ($n, $maxpart) = @_;
        return [] if $n < 0;
        return [[]] if $n == 0;
        my $partitions = [];
        foreach my $part (grep {$_<=$maxpart} @parts) {
                my $subpartitions = partmax($n - $part, $part);
                foreach (@$subpartitions) {
                        unshift @$_, $part;
                }
                push @$partitions, @$subpartitions;
        }
        return $partitions;
}

my $example = partitions shift;
print "count: ", scalar @$example, "\n";

foreach my $partition (@$example) {
        print join(" ", @$partition), "\n";
}
[download]