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.

## 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$$.

## References¶

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