Tom Pledger wrote:
We've seen some nice concise solutions that can deal with the original problem:
solve 1505 [215, 275, 335, 355, 420, 580]
I'll be a nuisance and bring up this case:
solve 150005 [2, 4, 150001]
A more scalable solution is to use an explicit heap that brings together all the ways to get to each partial sum. I coded one using Data.Map, but it's a bit long-winded and ugly.
How about import Data.Map as Map xkcd purse xs = foldl' (flip add) (Map.fromList [(0,[])]) xs ! purse where add price = Map.unionsWith (++) . take (purse `div` price + 1) . iterate (additem price) additem price = Map.map (map (price:)) . Map.mapMaybeWithKey clip . Map.mapKeysMonotonic (price +) clip cost x = if cost <= purse then Just x else Nothing Regards, apfelmus