, and the question is to decide whether any subset of the integers sum to precisely
Moreover, some restricted variants of it are NP-complete too, for example:[1] 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.
The complexity of the best known algorithms is exponential in the smaller of the two parameters n and L. The problem is NP-hard even when all input integers are positive (and the target-sum T is a part of the input).
[2] It can also be proved by reduction from 3-dimensional matching (3DM):[3] The following variants are also known to be NP-hard: The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is #P-complete.
[4] There are several ways to solve SSP in time exponential in n.[5] 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 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 run-time can be improved by several heuristics:[5] In 1974, Horowitz and Sahni[6] published a faster exponential-time algorithm, which runs in time
Using even the fastest comparison sorting algorithm, Mergesort for this step would take time
)th element, and these two sorted lists can be merged in time
Thus, each list can be generated in sorted form in time
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).
[7]) In 1981, Schroeppel and Shamir presented an algorithm[8] based on Horowitz and Sanhi, that requires similar runtime -
given 4 lists of length k. 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.
[5] In 2010, Howgrave-Graham and Joux[9] presented a probabilistic algorithm that runs faster than all previous ones - in time
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. The techniques of Howgrave-Graham and Joux were subsequently extended[10] bringing the time complexity to
SSP can be solved in pseudo-polynomial time using dynamic programming.
Suppose we have the following sequence of elements in an instance: We define a state as a pair (i, s) of integers.
For example, if all input values are positive and bounded by some constant C, then B is at most N C, so the time required is
This solution does not count as polynomial time in complexity theory because
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.
[14] In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having
A comparison of practical results and the solution of hard instances of the SSP is discussed by Curtis and Sanches.
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.
Recall that n is the number of inputs and T is the upper bound to the subset sum.
Note that without the trimming step (the inner "for each" loop), the list L would contain the sums of all
The trimming step does two things: These properties together guarantee that the list L contains no more than
Each trimming step introduces an additive error of at most
The above algorithm provides an exact solution to SSP in the case that the input numbers are small (and non-negative).
If any sum of the numbers can be specified with at most P bits, then solving the problem approximately with