Coins

Implementation



In [1]:

    
ways :: Int -> [Int] -> Int
ways _ [] = 0
ways 0 _ = 1
ways amount coins
    | amount < 0 = 0
    | otherwise =
        ways (amount - head coins) coins +
        ways amount (tail coins)



In [2]:

    
ways 10 [50, 25, 10, 5, 1]

Tests



In [3]:

    
import Data.List



In [4]:

    
combosGen :: Int -> [Int] -> [[Int]]
combosGen 0 _ = [[]]
combosGen _ [] = [[]]
combosGen amount coins =
    let
        allCoins = concatMap (\x -> replicate (amount `div` x) x) coins
    in
        nub $ subsequences allCoins



In [5]:

    
filter ((== 7) . sum) $ combosGen 7 [5, 2, 1]









    





[[5,2],[2,2,2,1],[5,1,1],[2,2,1,1,1],[2,1,1,1,1,1],[1,1,1,1,1,1,1]]



In [6]:

    
ways' :: Int -> [Int] -> Int
ways' _ [] = 0
ways' 0 _ = 1
ways' amount coins
    | amount < 0 = 0
    | otherwise = length $ filter ((== amount) . sum) $ combosGen amount coins



In [7]:

    
ways' 10 [50, 25, 10, 5, 1]