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