Subset sum problem

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S {\displaystyle S} of integers and a target-sum T {\displaystyle T} , and the question is to decide whether any subset of the integers sum to precisely T {\displaystyle T} . The problem is known to be NP-complete. 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 {\displaystyle T=0} . For example, given the set { − 7 , − 3 , − 2 , 9000 , 5 , 8 } {\displaystyle \{-7,-3,-2,9000,5,8\}} , the answer is yes because the subset { − 3 , − 2 , 5 } {\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., T = 1 2 ( a 1 + ⋯ + a n ) {\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.