# ...counted!

You will pass your program a variable which represents a quantity of money in dollars and/or cents and an array of coin values. Your challenge is to output the number of possible combinations of the given array of coin values that would add up to the amount passed to the code. If it is not possible with the coins named, the program should return 0.

Note on American numismatic terminology:

• 1-cent coin: penny
• 5-cent coin: nickel
• 10-cent coin: dime
• 25-cent coin: quarter (quarter dollar)

Example 1:

Program is passed:

12, [1, 5, 10]


(12 cents)

Output:

4


There are 4 possible ways of combining the coins named to produce 12 cents:

1. 12 pennies
2. 1 nickel and 7 pennies
3. 2 nickels and 2 pennies
4. 1 dime and 2 pennies

Example 2:

Program is passed:

26, [1, 5, 10, 25]


(26 cents)

Output:

13


There are 13 possible ways of combining the coins named to produce 26 cents:

1. 26 pennies
2. 21 pennies and 1 nickel
3. 16 pennies and 2 nickels
4. 11 pennies and 3 nickels
5. 6 pennies and 4 nickels
6. 1 penny and 5 nickels
7. 16 pennies and 1 dime
8. 6 pennies and 2 dimes
9. 11 pennies, 1 dime, and 1 nickel
10. 6 pennies, 1 dime, and 2 nickels
11. 1 penny, 1 dime, and 3 nickels
12. 1 penny, 2 dimes, and 1 nickel
13. 1 quarter and 1 penny

Example 3:

Program is passed:

19, [2, 7, 12]


Output:

2


There are 2 possible ways of combining the coins named to produce 19 cents:

1. 1 12-cent coin and 1 7-cent coin
2. 1 7-cent coin and 6 2-cent coins

Example 4:

Program is passed:

13, [2, 8, 25]


Output:

0


There are no possible ways of combining the coins named to produce 13 cents.

This has been through the Sandbox. Standard loopholes apply. This is code golf, so the answer with the fewest bytes wins.

• s/counted/earned Oct 20 '16 at 20:56
• @mbomb007 For four bytes: s/count/earn. Oct 21 '16 at 6:04
• For me and I guess for other people who don't pay with dollars it's not obvious what a nickel and a dime is. It wasn't hard to figure it out, but maybe you could write it a bit more international? Oct 21 '16 at 7:59
• @Kritzefitz. I've added that to the question.
– TRiG
Oct 21 '16 at 12:04
• @jpaugh: While coin-o-philes might agree, I'd have to disagree. A penny is the standard coin that has a value of one cent. Fifty-four cents is an amount of money. Fifty-four pennies is explicitly fifty-four coins. It's also called a "one-cent coin", or (officially) a "one-cent piece". I can't think of any formal setting where the word "penny" would be unacceptable. These people, who are specifically about collecting coins, have no problem calling it a "penny". Oct 22 '16 at 1:20

s#l@(c:d)|s>=c=(s-c)#l+s#d
s#_=0^s


Usage example: 26 # [1,5,10,25] -> 13.

Simple recursive approach: try both the next number in the list (as long as it is less or equal to the amount) and skip it. If subtracting the number leads to an amount of zero, take a 1 else (or if the list runs out of elements) take a 0. Sum those 1s and 0s.

Edit: @Damien: saved 3 bytes by pointing to a shorter base case for the recursion (which also can be found in @xnors answer).

• s#l@(c:d)|s>=c=(s-c)#l+s#d;s#_=0^s Oct 21 '16 at 7:57
• and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code
– user58988
Oct 22 '16 at 7:11
• @RosLuP: 1209 # [1,5,10,33,48]-> 1314050.
– nimi
Oct 22 '16 at 10:09
• @nimi ok for 1314050 I have the same result here... Thanks...
– user58988
Oct 22 '16 at 10:30
• @RosLuP: ... 537min later: 6000 # [1,5,10,33] -> 22086484.
– nimi
Oct 22 '16 at 21:30

## Mathematica, 35 22 bytes

Thanks to miles for suggesting FrobeniusSolve and saving 13 bytes.

Length@*FrobeniusSolve


Evaluates to an unnamed function, which takes the list of coins as the first argument and the target value as the second. FrobeniusSolve is a shorthand for solving Diophantine equations of the form

a1x1 + a2x2 + ... + anxn = b

for the xi over the non-negative integers and gives us all the solutions.

• @RosLuP You will need access to Mathematica to run this. Also this is an anonymous function so to call it, either encapsulate it in parentheses or store it to a variable. For example, (Length@*FrobeniusSolve)[{1, 7, 9}, 18] Oct 21 '16 at 21:07
• and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code
– user58988
Oct 22 '16 at 7:12
• @RosLuP 1314050 and 22086484, respectively. Oct 22 '16 at 11:30
• Ok here result the same, thanks...
– user58988
Oct 22 '16 at 11:46
• 16 votes for this are justified only if the programmer that wrote Length @ * FrobeniusSolve are you...
– user58988
Sep 2 '17 at 19:11

# Jelly (fork), 2 bytes

æf


This relies on a branch of Jelly where I was working on implementing Frobenius solve atoms so unfortunately you cannot try it online.

## Usage

$./jelly eun 'æf' '12' '[1,5,10]' 4$ ./jelly eun 'æf' '26' '[1,5,10,25]'
13
$./jelly eun 'æf' '19' '[2,7,12]' 2$ ./jelly eun 'æf' '13' '[2,8,25]'
0


## Explanation

æf  Input: total T, denominations D
æf  Frobenius count, determines the number of solutions
of nonnegative X such that X dot-product D = T

• ...that's not even fair. Oct 20 '16 at 21:22
• ...and I bet it's much faster! Oct 20 '16 at 22:21

# Pyth, 8 bytes

/sM{yS*E


Raw brute force, too memory intensive for actual testing. This is O(2mn), where n is the number of coins and m is the target sum. Takes input as target\n[c,o,i,n,s].

/sM{yS*EQQ      (implicit Q's)
*EQ       multiply coin list by target
S          sort
y           powerset (all subsequences)
{            remove duplicates
sM             sum all results
/        Q      count correct sums


s%(h:t)=sum$map(%t)[s,s-h..0] s%_=0^s  Using some multiple of the first coin h decreases the required sum s to a non-negative value in the decreasing progression [s,s-h..0], which then must be made with the remaining coins. Once there's no coins left, check that the sum is zero arithmetically as 0^s. • It's amazing how you hit exactly the same byte count as @nimi using a different approach. Oct 21 '16 at 8:03 ## JavaScript (ES6), 51 48 bytes f=(n,a,[c,...b]=a)=>n?n>0&&c?f(n-c,a)+f(n,b):0:1  Accepts coins in any order. Tries both using and not using the first coin, recursively calculating the number of combinations either way. n==0 means a matching combination, n<0 means that the coins exceed the quantity while c==undefined means that there are no coins left. Note that the function is very slow and if you have a penny coin then the following function is faster (don't pass the penny coin in the array of coins): f=(n,a,[c,...b]=a)=>c?(c<=n&&f(n-c,a))+f(n,b):1  • ...dangit. Real nice idea. Oct 21 '16 at 1:05 • and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code – user58988 Oct 22 '16 at 7:12 • @RosLuP The given code eventually returns 1314050 for your first example. My interpreter can't handle the recursion necessary to evaluate the second example. – Neil Oct 22 '16 at 10:27 • @RosLuP I modified the function to assume an additional penny coin exists and that returned 22086484 for 6000[5,10,33]. – Neil Oct 22 '16 at 10:31 • @Neil ok 22086484 for 6000[1,5,10,33]... Instead would be 11239 here for 6000[5,10,33] (the array you wrote) – user58988 Oct 22 '16 at 10:38 ## Perl, 45 bytes Byte count includes 44 bytes of code and -p flag. s%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{  Takes the coin values on the first line, and the targeted amount on the second line : $ perl -pE 's%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{' <<< "1 5 10 25
26"
13


Short explanations:

-p                        # Set $_ to the value of the input, # and adds a print at the end of the code. s%\S+%(1{$&})*%g,         # Converts each number n to (1{$&})* (to prepare the regex) # This pattern does half the job. (1x<>) # Converts the target to unary representation. =~ # Match against.. (regex) /^$_ $#$_ contains the pattern we prepared with the first line.
(?{$\++}) # Count the number of successful matches ^ # Forces a fail in the regex since the begining can't be matched here. /x # Ignore white-spaces in the regex # (needed since the available coins are space-separated) }{ # End the code block to avoid the input being printed (because of -p flag) # The print will still be executed, but$_ will be empty,
# and only $\ will be printed (this variable is added after every print)  # Jelly, 10 9 bytes œċÐ€S€€Fċ  Try it online! ### How? œċÐ€S€€Fċ - Main link: coins, target Ð€ - map over right argument, or for each n in [1,2,...,target] œċ - combinations with replacement, possible choices of each of n coins S€€ - sum for each for each (values of those selections) F - flatten into one list ċ - count occurrences of right argument  • +1 for using that many Euro-symbols in a money-related question. Oct 21 '16 at 9:48 # JavaScript (ES6), 59 bytes f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),0):1  Coins are input from highest to lowest, e.g. f(26,[100,25,10,5,1]). If you have a penny, remove it and use this much faster version instead: f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1  This uses a recursive formula much like @nimi's. I originally wrote this a few days ago when the challenge was still in the sandbox; it looked like this: f=(n,c=[100,25,10,5])=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1  The only differences being the default value of c (it had a set value in the original challenge), and changing the 0 in the .reduce function to 1 (this was two bytes shorter and a bazillion times faster than c=[100,25,10,5,1]). Here's a modified version which outputs all combinations, rather than the number of combinations: f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:[...x,...f(n-y,c.slice(i)).map(c=>[...c,y])],[]):[[]]  • and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code – user58988 Oct 22 '16 at 7:13 • @RosLuP I get 1314050 (after 5 minutes) and a stack overflow (after an hour), respectively. With the faster version I just added, I get 1314050 and 22086484 within a few seconds. Oct 22 '16 at 16:17 • With my old Pentium 2.8Gh computer 6 seconds for the first result, for the second 5 minutes +or - – user58988 Oct 22 '16 at 16:30 # PHP, 327 Bytes function c($f,$z=0){global$p,$d;if($z){foreach($p as$m){for($j=0;$j<=$f/$d[$z];){$n=$m;$n[$d[$z]]=$j++;$p[]=$n;}}}else for($p=[],$j=0;$j<=$f/$d[$z];$j++)$p[]=[$d[$z]=>$j];if($d[++$z])c($f,$z);}$d=$_GET[a];c($e=$_GET[b]);foreach($p as$u){$s=0;foreach($u as$k=>$v)$s+=$v*$k;if($s==$e&count($u)==count($d))$t[]=$u;}echo count($t);


Try it

## Axiom, 63 62 bytes

1 byte saved by @JonathanAllan

f(n,l)==coefficient(series(reduce(*,[1/(1-x^i)for i in l])),n)


This approach uses generating functions. Probably that didn't help bring down the code size. I think this is the first time that in my playing with Axiom I went as far as defining my own function.

The first time the function is called it gives a horrendous warning, but still produces the correct result. After that, everything is fine as long as the list isn't empty.

• I don't know Axiom - is it possible to remove the space before for? Oct 20 '16 at 22:49
• @JonathanAllan Yes, it is! Good golfing instinct, thanks! Oct 20 '16 at 23:00

# R, 8176 63 bytes

Thanks to @rturnbull for golfing away 13 bytes!

function(u,v)sum(t(t(expand.grid(lapply(u/v,seq,f=0))))%*%v==u)


Example (note that c(...) is how you pass vectors of values to R):

f(12,c(1,5,10))
[1] 4


Explanation:

u is the desired value, v is the vector of coin values.

expand.grid(lapply(u/v,seq,from=0))


creates a data frame with every possible combination of 0 to k coins (k depends on the denomination), where k is the lowest such that k times the value of that coin is at least u (the value to achieve).

Normally we would use as.matrix to turns that into a matrix, but that is many characters. Instead we take the transpose of the transpose (!) which automatically coerces it, but takes fewer characters.

%*% v then calculates the monetary value of each row. The last step is to count how many of those values are equal to the desired value u.

Note that the computational complexity and memory requirements of this are horrific but hey, it's code golf.

• Nice use of expand.grid! And I love the t(t()) trick. Since your function only involves a single line of code, you can remove the curly braces, saving you 2 bytes. Also, you can switch do.call(expand.grid,lapply(u/v,seq,from=0)) for just expand.grid(lapply(u/v,seq,f=0)), saving 11 bytes. Oct 21 '16 at 9:59
• Thanks for those! I never realised expand.grid would take a list as input. It's a bit of a shame that ":" doesn't work well with non-integers otherwise lapply(u/v,":",0) would have saved a couple more.
– JDL
Oct 21 '16 at 10:08
• do.call(x,y) is the same as x(y), so it's not about what kinds of input are accepted. If you really want to use :, I suppose you could use lapply(u%/%v,:,0), but it's the same byte count. Oct 21 '16 at 10:28
• "do.call(x,y) is the same as x(y)" --- only if y isn't a list, which it is in this case. Agree on your second point, though.
– JDL
Oct 21 '16 at 10:31

# J, 27 bytes

1#.[=](+/ .*~]#:,@i.)1+<.@%


## Usage

   f =: 1#.[=](+/ .*~]#:,@i.)1+<.@%
12 f 1 5 10
4
26 f 1 5 10 25
13
19 f 2 7 12
2
13 f 2 8 25
0


## Explanation

1#.[=](+/ .*~]#:,@i.)1+<.@%  Input: target T (LHS), denominations D (RHS)
%  Divide T by each in D
<.@   Floor each
These are the maximum number of each denomination
1+      Add 1 to each, call these B
,@i.         Forms the range 0 the the product of B
]               Get B
#:             Convert each in the range to mixed radix B
]                       Get D
+/ .*~                Dot product between D and each mixed radix number
These are all combinations of denominations up to T
[                         Get T
=                        Test if each sum is equal to T
1#.                          Convert as base 1 digits to decimal (takes the sum)
This is the number of times each sum was true

• J is so awesome, yet also, so insane Oct 21 '16 at 0:18

# TSQL, 105 bytes

This can only handle up to one dollar with these 4 coin types. The ungolfed version can handle up to around 4 dollars, but very slow - on my box this takes 27 seconds. Result is 10045 combinations b.t.w.

Golfed:

DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)
;WITH c as(SELECT 0l,0s UNION ALL SELECT z,s+z FROM c,@t WHERE l<=z and s<@)SELECT SUM(1)FROM c WHERE s=@


Ungolfed:

-- input variables
DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)

-- query
;WITH c as
(
SELECT 0l,0s
UNION ALL
SELECT z,s+z
FROM c,@t
WHERE l<=z and s<@
)
SELECT SUM(1)
FROM c
WHERE s=@
-- to allow more than 100 recursions(amounts higher than 1 dollar in this example)
OPTION(MAXRECURSION 0)


Fiddle

## tinylisp repl, 66 bytes

(d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1


Recursive solution: tries using the first coin and not using the first coin, then adds the results from each. Exponential time complexity and no tail-recursion, but it computes the test cases just fine.

Ungolfed (key to builtins: d = define, q = quote, i = if, l = less-than, s = subtract, h = head, t = tail):

(d combos
(q
((amount coin-values)
(i amount
(i (l amount 0)
0
(i coin-values
(s
(combos
(s amount (h coin-values))
coin-values)
(s
0
(combos
amount
(t coin-values))))
0))
1))))


Example usage:

tl> (d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1
C
tl> (C 12 (q (1 5 10)))
4
tl> (C 26 (q (1 5 10 25)))
13
tl> (C 19 (q (2 7 12)))
2
tl> (C 13 (q (2 8 25)))
0
tl> (C 400 (q (1 5 10 25)))
Error: recursion depth exceeded. How could you forget to use tail calls?!


# PHP, 130 bytes

function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));


99 byte recursive function (and 31 bytes of calling it) that repeatedly removes the value of the current coin from the target and calls itself with the new value and the other coins. Counts the number of times the target reaches 0 exactly. Run like:

 php -r "function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));" 12 1 5 10

• If called with more than 97 different types of coin it will die a recursion death without returning anything but as that's far more different types of coin then we have to support it's fine. Oct 21 '16 at 16:33

## Racket 275 bytes

(set! l(flatten(for/list((i l))(for/list((j(floor(/ s i))))i))))(define oll'())(for((i(range 1(add1(floor(/ s(apply min l)))))))
(define ol(combinations l i))(for((j ol))(set! j(sort j >))(when(and(= s(apply + j))(not(ormap(λ(x)(equal? x j))oll)))(set! oll(cons j oll)))))oll


Ungolfed:

(define(f s l)
(set! l              ; have list contain all possible coins that can be used
(flatten
(for/list ((i l))
(for/list ((j
(floor
(/ s i))))
i))))
(define oll '())                    ; final list of all solutions initialized
(for ((i (range 1
(floor             ; for different sizes of coin-set
(/ s
(apply min l)))))))
(define ol (combinations l i))          ; get a list of all combinations
(for ((j ol))                           ; test each combination
(set! j (sort j >))
(when (and
(= s (apply + j))              ; sum is correct
(not(ormap                     ; solution is not already in list
(lambda(x)
(equal? x j))
oll)))
(set! oll (cons j oll))             ; add found solution to final list
)))
(reverse oll))


Testing:

(f 4 '[1 2])
(println "-------------")
(f 12 '[1 5 10])
(println "-------------")
(f 19 '[2 7 12])
(println "-------------")
(f 8 '(1 2 3))


Output:

'((2 2) (2 1 1) (1 1 1 1))
"-------------"
'((10 1 1) (5 5 1 1) (5 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1 1 1))
"-------------"
'((12 7) (7 2 2 2 2 2 2))
"-------------"
'((3 3 2) (2 2 2 2) (3 2 2 1) (3 3 1 1) (2 2 2 1 1) (3 2 1 1 1) (2 2 1 1 1 1) (3 1 1 1 1 1) (2 1 1 1 1 1 1) (1 1 1 1 1 1 1 1))


Following recursive solution has some error:

(define (f s l)                      ; s is sum needed; l is list of coin-types
(set! l (sort l >))
(define oll '())                   ; list of all solution lists
(let loop ((l l)
(ol '()))               ; a solution list initialized
(when (not (null? l))
(set! ol (cons (first l) ol)))
(define ols (apply + ol))        ; current sum in solution list
(cond
[(null? l) (remove-duplicates oll)]
[(= ols s) (set! oll (cons ol oll))
(loop (rest l) '())
]
[(> ols s) (loop (rest l) (rest ol))
(loop (rest l) '())
]
[(< ols s) (loop l ol)
(loop (rest l) ol)
])))


Does not work properly for:

(f 8 '[1 2 3])


Output:

'((1 1 1 2 3) (1 2 2 3) (1 1 1 1 1 1 1 1) (2 3 3) (1 1 1 1 1 1 2) (1 1 1 1 2 2) (1 1 2 2 2) (2 2 2 2))


(1 1 3 3) is possible but does not come in solution list.

• I'm not familiar with Racket, but I did write a solution in Clojure for a similar problem to this a few years ago that made use of reduce Oct 22 '16 at 2:26
• 'reduce' is not part of base Racket language, although 'fold' is available. I have added a modified solution above since earlier solution has some error.
– rnso
Oct 22 '16 at 4:13
• Looks like a bunch of Lisp enthusiasts got together...and made a racket
– Joe
Sep 19 '17 at 16:12
• Some of Lisp enthusiasts first made a Scheme (groups.csail.mit.edu/mac/projects/scheme) which finally led to full-blown Racket (racket-lang.org , stackoverflow.com/questions/3345397/…) !
– rnso
Sep 19 '17 at 16:36

# Jelly, 15 bytes

s+\Fṁḷ
2*BW;ç/Ṫ


This was more of an exercise in writing an efficient version in Jelly without using builtins. This is based on the typical dynamic programming approach used to calculate the number of ways for making change

## Explanation

s+\Fṁḷ  Helper link. Input: solutions S, coin C
s       Slice the solutions into non-overlapping sublists of length C
+\     Cumulative sum
F    Flatten
ḷ  Left, get S
ṁ   Mold the sums to the shape of S

2*BW;ç/Ṫ  Main link. Input: target T, denominations D
2*        Compute 2^T
B       Convert to binary, creates a list with 1 followed by T-1 0's
These are the number of solutions for each value from 0 to T
starting with no coins used
W      Wrap it inside another array
;     Concatenate with D
ç/   Reduce using the helper link
Ṫ  Tail, return the last value which is the solution


# Actually, 15 bytes

Golfing suggestions welcome. Try it online!

╗;R╜∙♂S╔♂ΣiMc


Ungolfing

         Implicit input n, then the list of coins a.
╗        Save a to register 0.
;R       Duplicate n and create a range [1..n] from that duplicate.
...M   Map the following function over that range. Variable i.
╜        Push a from register 0.
∙        Push the i-th Cartesian power of a.
♂S       Sort each member of car_pow.
╔        Uniquify car_pow so we don't count too any duplicate coin arrangements.
♂Σ       Take the sum of each coin arrangement.
i        Flatten the list.
c        Using the result of the map and the remaining n, push map.count(n).
Implicit return.


# Python, 120 bytes

from itertools import*
lambda t,L:[sum(map(lambda x,y:x*y,C,L))-t for C in product(range(t+1),repeat=len(L))].count(0)


Bruteforces through all combinations of coins up to target value (even if the smallest is not 1).