Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Something went wrong with that request. Please try again.