Anonymous user
Subset sum problem: Difference between revisions
m
→{{header|Haskell}}: make it find sums other than 0, too
m (→{{header|Haskell}}: make it find sums other than 0, too) |
|||
Line 501:
None bruteforce: the list of numbers used here are different, and difficult for a bruteforce method.
<lang haskell>subsum want = foldl sub_ [(
sub_ a x = merge a $ map f a where
f (a,l) = (a+x, l++[x])
-- keep list of sums sorted
merge [] a = a
merge a [] = a
Line 512:
| av == bv = (bv,bl):merge as bs
| otherwise = (bv,bl):merge a bs
items = [-61, 1, 32, 373, 311, 249, 311, 32, -92, -185, -433,
-402, -247, 156, 125, 249, 32, -464, -278, 218, 32, -123,
-216, 373, -185, -402, 156, -402, -61, -31, 902 ]
main = print $ snd.head.filter ((==0).fst) $ subsum 0 items</lang>
{{out}}
<pre>
| |||