#!/usr/bin/perl
use strict;
use warnings;

my $desired_postage = $ARGV[0] || 1.51;
$desired_postage = int $desired_postage * 100;

my @stamps = 
	sort { $a <=> $b } 
	grep { chomp; $_ < $desired_postage } 
    map  { int $_ * 100 }
	grep { ! /^#/ } 
	<DATA>;

my $exact = grep { $_ == $desired_postage } @stamps;
print "Exact postage: " . $exact / 100 . "\n" if $exact;

my $dim_max = 6;
recurse( $desired_postage, [] );

sub recurse {
    my( $rest, $select ) = @_;
    if ( $rest == 0 ) {
        print $_ / 100 . " " for @$select;
        print "\n";
        return;
    }
    return if @$select >= $dim_max;

    my @filtered = grep { 
        $_ >= $rest / ($dim_max - @$select) 
        and $_ <= $rest 
    } @stamps;
    @filtered = grep{ $_ <= $select->[-1] } @filtered if $select->[-1];

    for my $stamp ( sort{ $b <=> $a } @filtered ) {
        recurse( $rest - $stamp, [ @$select, $stamp ] );
    }
    return;
}