Subset sum problem

The run-time complexity of the subset sum problem depends on two parameters: n - the number of input integers, and L - the precision of the problem, stated as the number of binary place values that it takes to state the problem.

• If n (the number of integers) is a small fixed number, then an exhaustive search for the solution is practical.
• If L (the number of binary digits) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.

When both n and L are large, the problem is NP-hard. The complexity of the best known algorithms is exponential in the smaller of the two parameters n and L. The following variants are known to be NP-hard:

• All input integers are positive (and the target-sum T is a part of the input). This can be proved by a direct reduction from 3SAT.[3][4]
• The input integers can be both positive and negative, and the target-sum T = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero. Given an instance (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value -T. Given a solution to the SubsetSumPositive instance, adding the -T yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the -T (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +T, which is a solution of the SubsetSumPositive instance.
• The input integers are positive, and T = sum(S)/2. This can also be proved by reduction from the general variant; see partition problem.

There are several ways to solve subset sum in time exponential in n.[5]

The problem can be solved in pseudo-polynomial time using dynamic programming. Suppose the sequence is

${\displaystyle x_{1},\ldots ,x_{N}}$

sorted in the increasing order and we wish to determine if there is a nonempty subset which sums to zero. Define the boolean-valued function ${\displaystyle Q(i,s)}$ to be the value (${\displaystyle true}$ or ${\displaystyle false}$) of

"there is a nonempty subset of ${\displaystyle x_{1},\ldots ,x_{i}}$ which sums to ${\displaystyle s}$."

Thus, the solution to the problem "Given a set of integers, is there a non-empty subset whose sum is zero?" is the value of ${\displaystyle Q(N,0)}$.

Let ${\displaystyle A}$ be the sum of the negative values and ${\displaystyle B}$ the sum of the positive values. Clearly, ${\displaystyle Q(i,s)=false}$, if ${\displaystyle s<A}$ or ${\displaystyle s>B}$. So these values do not need to be stored or computed.

Create an array to hold the values ${\displaystyle Q(i,s)}$ for ${\displaystyle 1\leq i\leq N}$ and ${\displaystyle A\leq s\leq B}$.

The array can now be filled in using a simple recursion. Initially, for ${\displaystyle A\leq s\leq B}$, set

${\displaystyle Q(1,s):=(x_{1}==s)}$

where ${\displaystyle ==}$ is a boolean function that returns true if ${\displaystyle x_{1}}$ is equal to ${\displaystyle s}$, false otherwise.

Then, for ${\displaystyle i=2,\ldots ,N}$, set

${\displaystyle Q(i,s):=Q(i-1,s)}$ or ${\displaystyle (x_{i}==s)}$ or ${\displaystyle Q(i-1,s-x_{i}),forA\leq s\leq B}$.

For each assignment, the values of ${\displaystyle Q}$ on the right side are already known, either because they were stored in the table for the previous value of ${\displaystyle i}$ or because ${\displaystyle Q(i-1,s-x_{i})=false}$ if ${\displaystyle s-x_{i}<A}$ or ${\displaystyle s-x_{i}>B}$. Therefore, the total number of arithmetic operations is ${\displaystyle O(N(B-A))}$. For example, if all the values are ${\displaystyle O(N^{k})}$ for some ${\displaystyle k}$, then the time required is ${\displaystyle O(N^{k+2})}$.

This algorithm is easily modified to return the subset with sum 0 if there is one.

The dynamic programming solution has runtime of ${\displaystyle O(sN)}$ where ${\displaystyle s}$ is the sum we want to find in set of ${\displaystyle N}$ numbers. This solution does not count as polynomial time in complexity theory because ${\displaystyle B-A}$ is not polynomial in the size of the problem, which is the number of bits used to represent it. This algorithm is polynomial in the values of ${\displaystyle A}$ and ${\displaystyle B}$, which are exponential in their numbers of bits.

For the case that each ${\displaystyle x_{i}}$ is positive and bounded by a fixed constant ${\displaystyle C}$, Pisinger found a linear time algorithm having time complexity ${\displaystyle O(NC)}$ (note that this is for the version of the problem where the target sum is not necessarily zero, otherwise the problem would be trivial).[9][10] In 2015, Koiliaris and Xu found a deterministic ${\displaystyle {\tilde {O}}(s{\sqrt {N}})}$ algorithm for the subset sum problem where ${\displaystyle s}$ is the sum we need to find.[11] In 2017, Bringmann found a randomized ${\displaystyle {\tilde {O}}(s)}$ time algorithm.[12]

In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having ${\displaystyle O(N(m-x_{\min })/p)}$ time and ${\displaystyle O(N+m-x_{\min })}$ space, where ${\displaystyle p}$ is the number of processing elements, ${\displaystyle m=\min(s,\sum x_{i}-s)}$ and ${\displaystyle x_{\min }}$ is the lowest integer.[13] This is the best theoretical parallel complexity known so far.

A comparison of practical results and the solution of hard instances of the SSP is discussed in.[14]

An approximate version of the subset sum would be: given a set of ${\displaystyle N}$ numbers ${\displaystyle x_{i},\ldots ,x_{N}}$ and a number ${\displaystyle s}$, output:

• Yes, if there is a subset that sums up to ${\displaystyle s}$.
• No, if there is no subset summing up to a number between ${\displaystyle (1-c)s}$ and ${\displaystyle s}$ for some small ${\displaystyle c>0}$.
• Any answer, if there is a subset summing up to a number between ${\displaystyle (1-c)s}$ and ${\displaystyle s}$ but no subset summing up to ${\displaystyle s}$.

If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in ${\displaystyle N}$ and ${\displaystyle 1/c}$.

The solution for subset sum also provides the solution for the original subset sum problem in the case where the numbers are small (again, for non-negative numbers). If any sum of the numbers can be specified with at most ${\displaystyle P}$ bits, then solving the problem approximately with ${\displaystyle c=2^{-P}}$ is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in ${\displaystyle N}$ and ${\displaystyle 2^{P}}$ (i.e., exponential in ${\displaystyle P}$).

The algorithm for the approximate subset sum problem is as follows:

initialize a list S to contain one element 0.

for each i from 1 to N do
    let T be a list consisting of xi + y, for all y in S
    let U be the union of T and S
    sort U
    make S empty 
    let y be the smallest element of U 
    add y to S
    for each element z of U in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than s.
        if y + cs/N < z ≤ s then
            y = z
            add z to S

if S contains a number between (1 − c)s and s then
    return yes
else
    return no

The algorithm is polynomial time because the lists ${\displaystyle S}$, ${\displaystyle T}$ and ${\displaystyle U}$ always remain of size polynomial in ${\displaystyle N}$ and ${\displaystyle 1/c}$ and, as long as they are of polynomial size, all operations on them can be done in polynomial time. The size of lists is kept polynomial by the trimming step, in which we only include a number ${\displaystyle z}$ into ${\displaystyle S}$ if it is greater than the previous one by ${\displaystyle cs/N}$ and not greater than ${\displaystyle s}$.

This step ensures that each element in ${\displaystyle S}$ is smaller than the next one by at least ${\displaystyle cs/N}$ and do not contain elements greater than ${\displaystyle s}$. Any list with that property consists of no more than ${\displaystyle N/c}$ elements.

The algorithm is correct because each step introduces an additive error of at most ${\displaystyle cs/N}$ and ${\displaystyle N}$ steps together introduce the error of at most ${\displaystyle cs}$.

• 3SUM
• Merkle–Hellman knapsack cryptosystem

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "35.5: The subset-sum problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, pg.223.