Subset sum problem

The subset sum problem (SSP) is a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>. In its most general formulation, there is a <a href="/facts/Multiset/bPFJGMDo">multiset</a> 
 
 
 
 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 <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a>. Moreover, some restricted variants of it are NP-complete too, for example:

<ul><li>The variant in which all inputs are positive.</li>
<li>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.</li>
<li>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 <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a>.</li></ul>
SSP can also be regarded as an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a>: 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 <a href="/facts/Knapsack_problem/HMIdVJH5">knapsack problem</a> and of the <a href="/facts/Multiple_subset_sum/5pgAVvpf">multiple subset sum</a> problem.

Subset sum problem open-in-new

Subset sum problem