-- Written by Mohit Jain

module Main where
import Data.List

pay total coins = payCoins total coinset where
                  addCoins = foldl (+) 0
                  makeTuples cs = (cs, addCoins cs)
                  coinset = map makeTuples (subsequences coins)

payCoins t l = findMinChange where
               showCoins [] = "Can not pay"
               showCoins (x:_) = "To pay = " ++ show t
                            ++ ", paying = " ++ show (fst x)
                            ++ ", Change = " ++ show (snd x - t)
               findMinChange = showCoins sortedFilteredList
               sortedFilteredList = sortBy myCmp filteredList
               myCmp x y = compare (snd x) (snd y)
               filteredList = filter (\x -> snd x >= t) l

main = putStrLn $ pay 100 [10, 10, 10, 20, 20, 30, 40, 50]

-- I got this error ERROR line 9 - Undefined variable "subsequences"
-- So I need to implement subsequences by my own :(
-- Copied from http://stackoverflow.com/questions/5373927/how-do-you-find-all-of-the-subsequences-of-a-list
subsequences            :: [a] -> [[a]]
subsequences xs         =  [] : nonEmptySubsequences xs

nonEmptySubsequences         :: [a] -> [[a]]
nonEmptySubsequences []      =  []
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
  where f ys r = ys : (x : ys) : r

To pay = 100, paying = [10,10,10,20,20,30], Change = 0