How to calculate the number of ways to represent n cents
This question already has an answer here:

How to find all combinations of coins when given some dollar value
32 answers
 Installed Ruby gems appear to exist on disk, but can't be found when run or referenced by other gems
 How to run git command remotely?
 Nested comments from scratch
 Ruby: new array from one value in an array of objects
 ActiveModel::MissingAttributeError occurs after deploying and then goes away after a while
 RSpec allow/expect vs just expect/and_return
3 Solutions collect form web for “How to calculate the number of ways to represent n cents”
We can see if your code is correct quite easily. let’s try making change for a dime. There are three ways: 1 dime, 1 nickel and 5 pennies, and 10 pennies, yet count_ways(10) #=> 9
.
You can do it as follows, using recursion.
Code
def count_ways(cents, coins)
if coins.size == 1
return (cents % coins.first) == 0 ? [cents/coins.first] : nil
end
coin, *remaining_coins = coins
(0..cents/coin).each_with_object([]) { n, arr
count_ways(centsn*coin, remaining_coins).each { a arr << [n, *a] } }
end
Examples
coins = [25, 10, 5, 1]
count_ways(32, coins)
#=> [[0, 0, 0, 32], [0, 0, 1, 27], [0, 0, 2, 22], [0, 0, 3, 17], [0, 0, 4, 12],
# [0, 0, 5, 7], [0, 0, 6, 2], [0, 1, 0, 22], [0, 1, 1, 17], [0, 1, 2, 12],
# [0, 1, 3, 7], [0, 1, 4, 2], [0, 2, 0, 12], [0, 2, 1, 7], [0, 2, 2, 2],
# [0, 3, 0, 2], [1, 0, 0, 7], [1, 0, 1, 2]]
count_ways(100, coins)
#=> [[0, 0, 0, 100], [0, 0, 1, 95], [0, 0, 2, 90], [0, 0, 3, 85], [0, 0, 4, 80],
# [0, 0, 5, 75], [0, 0, 6, 70], [0, 0, 7, 65], [0, 0, 8, 60], [0, 0, 9, 55],
# ...
# [3, 1, 2, 5], [3, 1, 3, 0], [3, 2, 0, 5], [3, 2, 1, 0], [4, 0, 0, 0]]
count_ways(100, coins).size
#=> 242
Explanation
The best way to show how the recursion works is to salt the code with puts statements and then run it against a simple example.
INDENT = 8
@indentation = 0
def indent
@indentation += INDENT
end
def undent
@indentation = [@indentationINDENT, 0].max
end
def ind
' '*@indentation
end
def count_ways(cents, coins)
puts "#{ind}** entering count_ways with cents=#{cents}, coins=#{coins}"
if coins.size == 1
puts "#{ind}<< returning [cents]=#{[cents]} as coins.size == 1"
undent
end
return [cents] if coins.size == 1
coin, *remaining_coins = coins
puts "#{ind}coin=#{coin}. remaining_coins=#{remaining_coins}"
puts "#{ind}0..cents/coin=#{0..cents/coin}"
arr = (0..cents/coin).each_with_object([]) do n, arr
puts "#{ind} n=#{n}, arr=#{arr}"
puts "#{ind} >> calling count_ways(#{cents}#{n}*#{coin}, remaining_coins)"
indent
aa = count_ways(centsn*coin, remaining_coins)
puts "#{ind} aa=#{aa}"
aa.each do a
arr << [n, *a]
puts "#{ind} arr << [#{n}, *#{a}], arr=#{arr}"
end
puts "#{ind} after all coins, arr=#{arr}"
end
puts "#{ind}<< returning arr=#{arr}"
undent
arr
end
Now let’s run count_ways(12, coins)
which should return the four ways of making change for 12
cents: [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
.
count_ways(12, coins)
** entering count_ways with cents=12, coins=[25, 10, 5, 1]
coin=25. remaining_coins=[10, 5, 1]
0..cents/coin=0..0
n=0, arr=[]
>> calling count_ways(120*25, remaining_coins)
** entering count_ways with cents=12, coins=[10, 5, 1]
coin=10. remaining_coins=[5, 1]
0..cents/coin=0..1
n=0, arr=[]
>> calling count_ways(120*10, remaining_coins)
** entering count_ways with cents=12, coins=[5, 1]
coin=5. remaining_coins=[1]
0..cents/coin=0..2
n=0, arr=[]
>> calling count_ways(120*5, remaining_coins)
** entering count_ways with cents=12, coins=[1]
<< returning [cents]=[12] as coins.size == 1
aa=[12]
arr << [0, *12], arr=[[0, 12]]
after all coins, arr=[[0, 12]]
n=1, arr=[[0, 12]]
>> calling count_ways(121*5, remaining_coins)
** entering count_ways with cents=7, coins=[1]
<< returning [cents]=[7] as coins.size == 1
aa=[7]
arr << [1, *7], arr=[[0, 12], [1, 7]]
after all coins, arr=[[0, 12], [1, 7]]
n=2, arr=[[0, 12], [1, 7]]
>> calling count_ways(122*5, remaining_coins)
** entering count_ways with cents=2, coins=[1]
<< returning [cents]=[2] as coins.size == 1
aa=[2]
arr << [2, *2], arr=[[0, 12], [1, 7], [2, 2]]
after all coins, arr=[[0, 12], [1, 7], [2, 2]]
<< returning arr=[[0, 12], [1, 7], [2, 2]]
aa=[[0, 12], [1, 7], [2, 2]]
arr << [0, *[0, 12]], arr=[[0, 0, 12]]
arr << [0, *[1, 7]], arr=[[0, 0, 12], [0, 1, 7]]
arr << [0, *[2, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
n=1, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
>> calling count_ways(121*10, remaining_coins)
** entering count_ways with cents=2, coins=[5, 1]
coin=5. remaining_coins=[1]
0..cents/coin=0..0
n=0, arr=[]
>> calling count_ways(20*5, remaining_coins)
** entering count_ways with cents=2, coins=[1]
<< returning [cents]=[2] as coins.size == 1
aa=[2]
arr << [0, *2], arr=[[0, 2]]
after all coins, arr=[[0, 2]]
<< returning arr=[[0, 2]]
aa=[[0, 2]]
arr << [1, *[0, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
<< returning arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
aa=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
arr << [0, *[0, 0, 12]], arr=[[0, 0, 0, 12]]
arr << [0, *[0, 1, 7]], arr=[[0, 0, 0, 12], [0, 0, 1, 7]]
arr << [0, *[0, 2, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2]]
arr << [0, *[1, 0, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
after all coins, arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
<< returning arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
=> [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
No, you will be doublecounting solutions, because you could first pick a quarter and then a dime or the other way around, but those solutions are essentially the same.
The easiest way to prevent doublecounting is to make sure you never pick a coin that is bigger than the ones you already picked.
In code:
def count_ways(n, max_coin)
return 0 if n < 0
return 1 if n == 0
result = count_ways(n1, 1)
result = result + count_ways(n 5, 5) if max_coin >= 5
result = result + count_ways(n10, 10) if max_coin >= 10
result = result + count_ways(n25, 25) if max_coin >= 25
result
end
And call it with 25 as initial max coin
The order of the coins doesn’t matter, so coins.min
isn’t going to help you in this case – it’s overcomplicating things.
First we must develop an intuition about the relationship between the kinds of coins and the amount of change to count
The number of ways to change amount
a
usingn
kinds of coins equals
 the number of ways to change amount
a
using all but the first kind of coin, plus the number of ways to change amount
a − d
using alln
kinds of coins, whered
is the denomination of the first kind of coin._{source: SICP Chapter 1.2}
### change_coins :: (Int, [Int]) > Int
def change_coins amount, (x,*xs)
if amount == 0
1
elsif amount < 0 or x.nil?
0
else
change_coins(amount, xs) + change_coins(amount  x, [x,*xs])
end
end
change_coins 11, [1, 2, 5] # => 11
change_coins 2, [3] # => 0
change_coins 100, [1, 5, 10, 25, 50] # => 292
Sensible return values
For example, in this problem we have to return 1 if the amount of money cannot be made up by any combination of the coins.
The 1
case is dumb. There are zero ways to change 2 cents using only a 3cent coin; therefore we return 0
.
If you really must return 1
, just use a stupid wrapper
def cc amount, xs
count = change_coins amount, xs
if count == 0 then 1 else count end
end
Order doesn’t matter
change_coins 11, [5, 1, 2] # => 11
change_coins 2, [3] # => 0
change_coins 100, [50, 1, 25, 10, 5] # => 292