The Subset Sum problem is a classical NP-Complete problem in computing and number theory. Given a set of integers, S, and a target value n, is there a subset of S that sums to exactly S.
Let S = {1, 2, 3, 4, 10, 11, 12, 14, 18, 20}, and a query of n=26.
- This would be satisfied by the subset: {2, 3, 10, 11}, as 2+3+10+11=26.
Note that the declaration of value(k ; k). in an instance.lp file will result in a single instance of k having property value. For simplicity this implementation was designed where S is a set, allowing inclusion, but not duplicates. For a multi-set-based implementation (see below), modification would be necessary.
There are several variants of this problem that are NP-Complete. Some assumptions in this encoding are:
- A set of values is encoded (vs. a multiset) because the encoding of values is a single predicate.
- Generating software is over positive integers (an arbitrary decision that should be easy to modify).
See also: