The subset sum problem (SSP) is a decision problem [Decision problem] in computer science. In its most general formulation, there is a multiset [Multiset] \(S\) of integers and a target-sum \(T\), and the question is to decide whether any subset of the integers sum to precisely \(T\). The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:

  • The variant in which all inputs are positive.
  • The variant in which inputs may be positive or negative, and \(T=0\). For example, given the set \(\{-7,-3,-2,9000,5,8\}\), the answer is yes because the subset \(\{-3,-2,5\}\) sums to zero.
  • The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., \(T=\frac {1}{2}}(a_{1}+\dots +a_{n})\) . This special case of SSP is known as the partition problem.

SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice.

SSP is a special case of the knapsack problem [Knapsack problem] and of the multiple subset sum problem.

(“Subset Sum Problem” 2023)

Pseudo-polynomial time time Dynamic programming solution

Algorithm

SSP can be solved in pseudo-polynomial time using dynamic programming. Suppose we have the following sequence of elements in an instance:

\(x_{1},\ldots ,x_{N}\)

We define a state as a pair \((i, s)\) of integers. This state represents the fact that

“there is a nonempty subset of \(x_{1},\ldots ,x_{i}\) which sums to \(s\).”

Each state \((i, s)\) has two next states:

  1. \((i+1, s)\), implying that \(x_{i+1}\) is not included in the subset
  2. \((i+1, s+ x_{i+1})\), implying that \(x_{i+1}\) is included in the subset

Starting from the initial state \((0, 0)\), it is possible to use any graph search algorithm (e.g. BFS) to search the state \((N, T)\). If the state is found, then by backtracking we can find a subset with a sum of exactly \(T\).

Pseudo-polynomial time subset sum problem implementation in Python.

Bibliography

References

“Subset Sum Problem.” 2023. Wikipedia, January. https://en.wikipedia.org/w/index.php?title=Subset_sum_problem&oldid=1136150450.