Create a gist now

Instantly share code, notes, and snippets.

DP solution to SICP Chapter 1.2 coin change problem.
coinChange :: [Int] -> [Int]
coinChange = foldr go (1: repeat 0) where
go coin xs = xs' where
(a, b) = splitAt coin xs
xs' = a ++ zipWith (+) xs' b
main = print $ coinChange [1,5,10,25,50] !! 100 -- prints 292
@WillNess

what I meant was this

change :: Int -> [Int] -> [[Int]]
change n xs 
     | n<0 || null xs = []
change n _  | n==0    = [[]]
change n (x:xs)       = change n xs ++ map (x:) (change (n - x) (x:xs))

-- *Main> length $ change 100 [1,5,10,25,50]   ==>  292

-- code from http://stackoverflow.com/a/21427171/849891 by András Kovács:

combsOf :: Int -> [a] -> [[a]]
combsOf n _ | n < 1 = [[]]
combsOf n (x:xs)    = combsOf n xs ++ map (x:) (combsOf (n - 1) xs)
combsOf _ _         = []

although it doesn't scale well, like your version in this gist does.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment