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$ of integers and a target-sum $T$, and the question is to decide whether any subset of the integers sum to precisely $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$. For example, given the set $\{-7,-3,-2,9000,5,8\}$, the answer is yes because the subset $\{-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={\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.

Computational hardness

The run-time complexity of SSP 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, SSP 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.
• 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.

Exponential time algorithms

There are several ways to solve SSP in time exponential in n.

Inclusion-Exclusion

The most naïve algorithm would be to cycle through all subsets of n numbers and, for every one of them, check if the subset sums to the right number. The running time is of order $O(2^{n}\cdot n)$, since there are $2^{n}$ subsets and, to check each subset, we need to sum at most n elements.

The algorithm can be implemented by depth-first search of a binary tree: each level in the tree corresponds to an input number; the left branch corresponds to excluding the number from the set, and the right branch corresponds to including the number (hence the name Inclusion-Exclusion). The memory required is $O(n)$. The run-time can be improved by several heuristics:

• Process the input numbers in descending order.
• If the integers included in a given node exceed the sum of the best subset found so far, the node is pruned.
• If the integers included in a given node, plus all remaining integers, are less than the sum of the best subset found so far, the node is pruned.

Horowitz and Sahni

Horowitz and Sahni published a faster exponential-time algorithm, which runs in time $O(2^{n/2}\cdot (n/2))$, but requires much more space - $O(2^{n/2})$. The algorithm splits arbitrarily the n elements into two sets of $n/2$ each. For each of these two sets, it stores a list of the sums of all $2^{n/2}$ possible subsets of its elements. Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time $O(2^{n/2}n)$. However, given a sorted list of sums for $k$ elements, the list can be expanded to two sorted lists with the introduction of a ($k+1$)th element, and these two sorted lists can be merged in time $O(2^{k})$. Thus, each list can be generated in sorted form in time $O(2^{n/2})$. Given the two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to T in time $O(2^{n/2})$. To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than T, the algorithm moves to the next element in the first array. If it is less than T, the algorithm moves to the next element in the second array. If two elements that sum to T are found, it stops.

Schroeppel and Shamir

Schroeppel and Shamir presented an algorithm based on Horowitz and Sanhi, that requires similar runtime - $O(2^{n/2}\cdot (n/4))$, much less space - $O(2^{n/4})$. Rather than generating all subsets of n/2 elements in advance, they partition the elements into 4 sets of n/4 elements each, and generate subsets of n/2 elements dynamically using a min heap.

Due to space requirements, the HS algorithm is practical for up to about 50 integers, and the SS algorithm is practical for up to 100 integers.

Howgrave-Graham and Joux

Howgrave-Graham and Joux presented a probabilistic algorithm that runs faster than all previous ones - in time $O(2^{n/3})$. It solves only the decision problem, cannot prove there is no solution for a given sum, and does not return the subset sum closest to T.

Pseudo-polynomial time dynamic programming solution

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

$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 $Q(i,s)$ to be the value ($true$ or $false$) of

"there is a nonempty subset of $x_{1},\ldots ,x_{i}$ which sums to $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 $Q(N,0)$.

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

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

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

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

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

Then, for $i=2,\ldots ,N$, set

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

For each assignment, the values of $Q$ on the right side are already known, either because they were stored in the table for the previous value of $i$ or because $Q(i-1,s-x_{i})=false$ if $s-x_{i}<A$ or $s-x_{i}>B$. Therefore, the total number of arithmetic operations is $O(N(B-A))$. For example, if all the values are $O(N^{k})$ for some $k$, then the time required is $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 $O(sN)$ where $s$ is the sum we want to find in set of $N$ numbers. This solution does not count as polynomial time in complexity theory because $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 $A$ and $B$, which are exponential in their numbers of bits.

For the case that each $x_{i}$ is positive and bounded by a fixed constant $C$, Pisinger found a linear time algorithm having time complexity $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). In 2015, Koiliaris and Xu found a deterministic ${\tilde {O}}(s{\sqrt {N}})$ algorithm for the subset sum problem where $s$ is the sum we need to find. In 2017, Bringmann found a randomized ${\tilde {O}}(s)$ time algorithm.

In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having $O(N(m-x_{\min })/p)$ time and $O(N+m-x_{\min })$ space, where $p$ is the number of processing elements, $m=\min(s,\sum x_{i}-s)$ and $x_{\min }$ is the lowest integer. 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 by Curtis and Sanches.

Polynomial time approximation algorithms

Suppose all inputs are positive. An approximation algorithm to SSP aims to find a subset of S with a sum of at most T and at least r times the optimal sum, where r is a number in (0,1) called the approximation ratio.

Simple 1/2-approximation

The following very simple algorithm has an approximation ratio of 1/2:

• Order the inputs by descending value;
• Put the next-largest input into the subset, as long as it fits there.

When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset, so it must be smaller than T/2. Therefore, the sum of inputs in the subset is more than T/2, which is obviously more than OPT/2.

Fully-polynomial time approximation scheme

The following algorithm attains, for every $\epsilon >0$, an approximation ratio of $(1-\epsilon )$. Its run time is polynomial in $n$ and $1/\epsilon$. Recall that n is the number of inputs and T is the upper bound to the subset sum.

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

Note that without the trimming step (the inner "for each" loop), the list L would contain the sums of all $2^{n}$ subsets of inputs. The trimming step does two things:

• It ensures that all sums remaining in L are below T, so they are feasible solutions to the subset-sum problem.
• It ensures that the list L is "sparse", that is, the difference between each two consecutive partial-sums is at least $\epsilon T/n$.

These properties together guarantee that the list $L$ contains no more than $n/\epsilon$ elements; therefore the run-time is polynomial in $n/\epsilon$.

When the algorithm ends, if the optimal sum is in $L$, then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step. Each trimming step introduces an additive error of at most $\epsilon T/n$, so $n$ steps together introduce an error of at most $\epsilon T$. Therefore, the returned solution is at least $OPT-\epsilon T$ which is at least $(1-\epsilon )OPT$ .

The above algorithm 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 $P$ bits, then solving the problem approximately with $\epsilon =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 $n$ and $2^{P}$ (i.e., exponential in $P$).

Another FPTAS for subset sum is available at .

Multiple subset sum problem

The multiple subset sum problem (MSSP) is a generalization of SSP in which we are allowed to select some m>1 subsets, where the sum in each subset is at most T. The problem has two variants:

• Max-sum MSSP: the goal is that the sum of all subsets is as large as possible.
• Max-min MSSP (also called bottleneck MSSP or BMSSP): the goal is that the smallest subset sum is as large as possible.

When m is variable (a part of the input), both problems are strongly NP-hard, by reduction from 3-partition. This means that they have no FPTAS unless P=NP.

Even when m=2, the problems do not have an FPTAS unless P=NP. This can be shown by a reduction from the equal-cardinality partition problem (EPART):

• Given an instance a₁,...,a_n of EPART with target sum T, construct an instance 2T+a₁, ..., 2T+a_n of MSSP with target sum (n+1)T for both subsets.
• A solution to EPART consists of two parts, each of which has n/2 elements with a sum of T. It corresponds to an optimal solution of both MSSP variants: two subsets with a sum of (n+1)T, which is the largest possible. Similarly, each optimal solution of MSSP corresponds to a solution to EPART.
• Any non-optimal solution to MSSP leaves at least one item unallocated, so its sum is at most 2nT and its minimum is at most nT. In both variants, the approximation ratio is at most $1-1/(n+1)$.
• Therefore, for any $\epsilon <1/(n+1)$, any algorithm with approximation ratio $(1-\epsilon )$ must find the optimal solution if it exists.
• If we had an FPTAS, then we would have an algorithm with e.g. $\epsilon =1/(n+2)$, with run-time polynomial in n. This algorithm could be used to solve EPART in time polynomial in n. But this is not possible unless P=NP.

The following approximation algorithms are known:

• For max-sum MSSP, with variable m: a PTAS, which runs in time O(m+n) when $\epsilon$ is fixed. The run-time is at least exponential in $1/\epsilon ^{2}$, and the authors consider it impractical.
• For max-min MSSP:
  • With variable m: a 2/3-approximation, in time O(n log n). No better approximation is possible unless P=NP (by reduction from 3-partition).
  • With fixed m: a PTAS, running in time $O(n^{2m/\epsilon })$.
  • With a fixed number of distinct input values: a PTAS using Lenstra's algorithm.

See also

• 3SUM
• Merkle–Hellman knapsack cryptosystem
• Fair subset sum problem.

Further reading

• 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.