In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1£1 + 150p + 220p + 15p + 12p + 31p
How many different ways can £2 be made using any number of coins?
% % Simply counting through the entire tree, brute-force % p31()-> Coins=[1,2,5,10,20,50,100,200], Results=array:set(0,1,array:new(201)), Ans=p31(0,Coins), io:format("~w~n",[Ans]). p31(N,_) when N>200->0; p31(N,_) when N==200->1; p31(N,[])->0; p31(N,[Avail|Rest])-> p31(N+Avail,[Avail|Rest])+p31(N,Rest).
def p31_count(n,coins) return 0 if coins.length==0 return 1 if(coins==[1]) total=0 ourCoin=coins[-1] leftover=coins[0...-1] 0.upto(n/ourCoin) do |taking| if(n==taking*ourCoin) total+=1 else total+=p31_count(n-taking*ourCoin,leftover) end end total end def p31 puts p31_count(200,[1,2,5,10,20,50,100,200]) end