CoinChange.hs

countChg :: Int -> [Int] -> Int
countChg 0 _ = 1 -- There is only one way of counting an amount of 0
countChg _ [] = 0 -- There are 0 ways to count for no coins
countChg amt coins@(c:cs)
  | amt < 0 = 0 -- This branch failed, we got something less than 0
  | otherwise = countChg amt cs + countChg (amt - c) coins -- Branch out into a branch with one less coin and 
                                                           -- a branch with the same number of coins but one coin 
                                                           -- reduced from the amount