A penny saved is a penny

Question

...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.

Answer 1

Haskell, 37 34 bytes

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).

Answer 2

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.

Answer 3

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

Answer 4

Pyth, 8 bytes

/sM{yS*E

Raw brute force, too memory intensive for actual testing. This is O(2^mn), 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

Answer 5

Haskell, 37 bytes

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.

Answer 6

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

Answer 7

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)

Answer 8

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

Answer 9

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])],[]):[[]]

Answer 10

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

Answer 11

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.

Answer 12

R, 81 76 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.

Answer 13

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

Answer 14

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

Answer 15

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?!

Answer 16

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

Answer 17

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  
                  (add1
                   (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.

Answer 18

Jelly, 15 bytes

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

Try it online! or Verify all test cases.

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

Answer 19

Actually, 15 bytes

Golfing suggestions welcome. Try it online!

╗;R`╜∙♂S╔♂Σi`Mc

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.

Answer 20

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).