1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu syntax=perl:
#
# Copyright (c) 2020 Bob Lied
# The copyright notice above does not evidence any actual
# or intended publication of such source code.
#===============================================================================
# CoinSum.pm
#
# Description:
#
#===============================================================================
package CoinSum;
use strict;
use warnings;
use 5.010;
use Carp;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT = qw(coinSum);
our @EXPORT_OK = qw();
my @ComboList;
sub _coinSum
{
my ($depth, $target, $coinList, $coin, $combo) = @_;
my $diff = $target - $coin;
# say " depth=$depth, target = $target, coin = $coin, diff = $diff, list = [ @$coinList ], combo = [ @$combo ]";
if ( $diff == 0 )
{
push @ComboList, [ @$combo ];
# say "FOUND [ @$combo ]";
return 0;
}
if ( $diff < 0 )
{
pop @$combo;
# say "TOO FAR";
return $diff;
}
my @remainingCoin = sort { $a < $b } grep { $_ <= $diff } @$coinList;
for my $denom ( @remainingCoin )
{
push @$combo, $denom;
_coinSum( $depth+1, $diff, \@remainingCoin, $denom, $combo );
pop @$combo;
}
}
sub coinSum
{
my ($sum, @coins) = @_;
# Sort denominations so largest is first.
@coins = sort { $a < $b } @coins;
while ( @coins )
{
# say "TOP: coin = $coins[0]";
_coinSum(1, $sum, \@coins, $coins[0], [ $coins[0] ] );
shift @coins;
}
return \@ComboList;
}
1;
|
