Anonymous user
Subset sum problem: Difference between revisions
→{{header|Haskell}}: non-bruteforce
m (→{{header|REXX}}: added whitespace, order subroutines in alphabetic order, added comments, changed comments, deleted superfluous semicolons. -- ~~~~) |
(→{{header|Haskell}}: non-bruteforce) |
||
Line 499:
{{out}}
<pre>["archbishop","gestapo"]</pre>
None bruteforce: the list of numbers used here are different, and difficult for a bruteforce method.
<lang haskell>subsum ls = sub_ [(0,[])] ls where
sub_ a [] = a
sub_ a (x:xs) = sub_ (merge a $ map (f x) a) xs
f x (a,l) = (a+x, l++[x])
-- keep list of sums sorted. Don't use standard sort!
merge [] a = a
merge a [] = a
merge a@((av,al):as) b@((bv,bl):bs)
| av < bv = (av,al):merge as b
| 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 items</lang>
{{out}}
<pre>
[-61,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,902]
</pre>
=={{header|Icon}} and {{header|Unicon}}==
| |||