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

[Tom Pledger]

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.  Perhaps a  
purpose-built heap monad would make it more elegant... as long as it  
could be reused elsewhere.  Just musing.  :-)

- Tom