arg, I've been working on the following (brute force regexp engine) solution for a while, but I can't get it to work. It finds some matches, then gives up. I suspect there's some kind of optimization in the regexp engine making it think it's done. I figured I'd post it in case someone else wants to tinker with it.

use strict;
use warnings;

use re 'eval';
#use re 'debug';

use Data::Dumper qw( Dumper );


my $amount = shift;

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


my $choices = join "\n   ",
              map { "(  .{$_} (?{ my \%r = \%{\$^R}; \$r{$_}++; +{ \%r
+ } })  )*" }
              @bills;

my $regexp = qr/
   ^
   (?{ +{} })
   $choices
   $
   (?{ push(@matches, $^R) })
   (?!)
/x;


print($regexp, "\n");

our @matches;
('.' x $amount) =~ $regexp;
print(Dumper(\@matches));
[download]

>perl 546453.pl 20
(?x-ism:
   ^
   (?{ +{} })
   (  .{1} (?{ my %r = %{$^R}; $r{1}++; +{ %r } })  )*
   (  .{5} (?{ my %r = %{$^R}; $r{5}++; +{ %r } })  )*
   (  .{10} (?{ my %r = %{$^R}; $r{10}++; +{ %r } })  )*
   (  .{20} (?{ my %r = %{$^R}; $r{20}++; +{ %r } })  )*
   (  .{50} (?{ my %r = %{$^R}; $r{50}++; +{ %r } })  )*
   (  .{100} (?{ my %r = %{$^R}; $r{100}++; +{ %r } })  )*
   $
   (?{ push(@matches, $^R) })
   (?!)
)
$VAR1 = [
          {
            '1' => '20'
          },
          {
            '1' => '15',
            '5' => '1'
          },
          {
            '1' => '10',
            '5' => '2'
          },
          {
            '1' => '10',
            '10' => '1'
          },
          {
            '1' => '5',
            '5' => '3'
          }
        ];
[download]

          {
            '1' => '5',
            '5' => '2'
            '10' => '1'
          },
          {
            '5' => '4'
          },
          {
            '5' => '2'
            '10' => '1'
          },
          {
            '10' => '2'
          },
          {
            '20' => '1',
          },
[download]