Subset sum problem

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

• The variant in which all inputs are positive.
• The variant in which inputs may be positive or negative, and ${\displaystyle T=0}$. For example, given the set ${\displaystyle \{-7,-3,-2,9000,5,8\}}$, the answer is yes because the subset ${\displaystyle \{-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., ${\displaystyle 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 and of the multiple subset sum problem.