Editing Subset sum problem (section)

{{Short description|Decision problem in computer science}}
The '''subset sum problem''' (SSP) is a [[decision problem]] in [[computer science]]. In its most general formulation, there is a [[multiset]] <math>S</math> of integers and a target-sum <math>T</math>, and the question is to decide whether any subset of the integers sum to precisely <math>T</math>''.''<ref name="kleinberg2006p491">{{cite book|last1=Kleinberg|first1=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=Algorithm Design|last2=Tardos|first2=Éva|year=2006|isbn=0-321-37291-3|edition=2nd|page=[https://archive.org/details/algorithmdesign0000klei/page/491 491]|url-access=registration}}</ref> The problem is known to be [[NP-completeness|NP-complete]]. Moreover, some restricted variants of it are NP-complete too, for example:<ref name="kleinberg2006p491" />

* The variant in which all inputs are positive.
* The variant in which inputs may be positive or negative, and <math>T=0</math>. For example, given the set <math>\{-7, -3, -2, 9000, 5, 8\}</math>, the answer is ''yes'' because the subset <math>\{-3, -2, 5\}</math> 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., <math> T = \frac{1}{2}(a_1+\dots+a_n)</math> .  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.