Re: [Haskell-cafe] xkcd #287 "NP-Complete"

Marc A. Ziegert wrote:

i see only two solutions.

let menu = [215, 275, 335, 355, 420, 580] let run x menu = [[c]|c<-menu,c==x]++[c:cs|c<-menu,c

-> [[215,215,215,215,215,215,215],[215,355,355,580]]

You are right, I saw many solutions but they were all equivalent to just those two. I did not avoid permutation-induced redundancy. I was unsure how to eliminate that redundancy. After reading your algorithm, I see it. Here is my algorithm modified. import Data.List import Control.Monad -- exactly n v -- items in v that sum to exactly n -- returns list of solutions, each solution list of items exactly :: (Real a) => a -> [a] -> [[a]] exactly 0 v = return [] exactly n v = do w@(c:w') <- tails v guard (c <= n) liftM (c :) (exactly (n - c) w) -- for solutions that use items at most once, -- change w to w' play = exactly 1505 menu menu = [215, 275, 335, 355, 420, 580]