A penny saved is a penny
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 1
s and 0
s.
Edit: @Damien: saved 3 bytes by pointing to a shorter base case for the recursion (which also can be found in @xnors answer).
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.
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