30 lines · 955 B · Standard ML
RawDownload
(* The subset sum problem				sestoft@dina.kvl.dk    Given a set (list) of integers we can find the sum of its elements.   The subset sum problem is: How many subsets of a set xs has sum s?    The answer can be computed as 	length (List.filter (fn ss => s = foldl (op+) 0 ss) (subsets4 xs))   but this is inefficient, since all the subsets must be built before    their sums are computed and checked.    A much faster solution is obtained by modifying Solution 4 in the   subset computation (see file subsets.sml).*) local    fun subsuma []      0       res = res + 1       | subsuma []      missing res = res      | subsuma (x::xr) missing res = 	subsuma xr missing (subsuma xr (missing-x) res)in    fun subsum xs sum = subsuma xs sum 0end; print "Try\n\      \     subsum [1,2,3] 3;\n\      \     subsum [1,2,3,~1,4] 3;\n\      \     subsum [] 3;\n\      \     subsum [] 0;\n\      \     subsum [1,2,3,4,5,6,7,8,~8,0,~14] 6;\n\n" 

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t