Subset sum problem: Difference between revisions

Content deleted Content added

Inline

@@ Line 501: / Line 501: @@
 None bruteforce: the list of numbers used here are different, and difficult for a bruteforce method.
-<lang haskell>subsum = foldl sub_ [(0,[])] where
+<lang haskell>subsum want = foldl sub_ [(-want,[])] where
 	sub_ a x = merge a $ map f a where
 		f (a,l) = (a+x, l++[x])
-	-- keep list of sums sorted. Don't use standard sort!
+	-- keep list of sums sorted and unique
 	merge [] a = a
 	merge a [] = a
@@ Line 512: / 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 items</lang>
+main = print $ snd.head.filter ((==0).fst) $ subsum 0 items</lang>
 {{out}}
 <pre>