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

[Albert Y. C. Lai]

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<x,cs<-run (x-c) (dropWhile (/=c) menu)]
> run 1505 menu
> 
> ->
> [[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]