(* 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"
(* 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 0
end;
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"