Subset sum problem
From Academic Kids

The subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, does any subset sum to exactly zero? For example, given the set { −7, −3, −2, 5, 8}, the answer is YES because the subset { −3, −2, 5} sums to zero. The problem is NPComplete, and is perhaps the simplest such problem to describe.
An equivalent problem is this: given a set of integers and an integer s, does any subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem.
Contents 
General discussion
The subset sum problem is a good introduction to the NPcomplete class of problems. There are two reasons for this
 It is a decision, and not an optimization problem and
 It has a very simple formal definition and problem statement.
Most physical problems can be solved with a +/ 1% error. Being asked to solve a subset sum problem for 100digit numbers with a precision of +/10^{−100} might seem silly and irrelevant. There are two reasons why this is not the case.
First, the subset sum problem gives a precise statement of the logical complexity of a class of problems (NPcomplete problems). Solving it exactly would mean solving all problems in this welldefined class. Solving it with +/ 1% error would mean that the algorithm would become useless for some of the other problems. Second, in at least one context, it is actually important to solve the subset sum problem exactly. In cryptography, Subset Sum problem comes up when a codebreaker attempts, given a message and ciphertext, to deduce the secret key. A key that is within +/ 1% of the real key is essentially useless for the codebreaker.
The cases when an approximate solution is sufficient have also been studied, in the field of approximation algorithms. One such algorithm for the subset sum problem is given below.
The complexity of subset sum
The complexity of subset sum can be viewed as depending on two parameters, N, the number of decision variables, and P, the precision of the problem (stated as the number of binary place values that it takes to state the problem).
The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. Thus, the problem is most difficult if N and P are of the same order but it only becomes easy if either N or P becomes very small. We give efficient algorithms for both of those cases below.
Exponential time algorithm
There are several ways to solve subset sum in time exponential in N. 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}N), since there are 2^{N} subsets and, to check each subset, we need to sum at most N elements.
A better exponential time algorithm is known, which runs in time O(2^{N/2}N). The algorithm splits the N elements into two sets of N/2 each. For each of these two sets, it calculates sums of all 2^{N/2} possible subsets of its elements and stores them in an array of length 2^{N/2}. It then sorts each of these two arrays, which can be done in time O(2^{N/2}N). When arrays are sorted, the algorithm can check if an element of the first array and an element of the second array sum up to s 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 s, the algorithm moves to the next element in the first array. If it is less than s, the algorithm moves to the next element in the second array. If two elements with sum s are found, it stops.
Pseudopolynomial time dynamic programming solution
The problem can be solved as follows using dynamic programming. Suppose the sequence is
 x_{1}, ..., x_{n}
and we wish to find a subset which sums to 0. Let N be the sum of the negative values and P the sum of the positive values. Define the boolean valued function
 Q(i,s)
to be the value (true or false) of
 "there a subset of x_{1}, ..., x_{i} which sums to s".
(Thus, the value we really want is Q(n,0).)
Clearly
 Q(i,s) = false
if s<N or s>P. Create an array to hold the values Q(i,s) for 1≤i≤n and N≤s≤P. The array can now be filled in using a simple recursion.
 Q(1,s) = "s=0 or x_{1}=s".
For i>1,
 Q(i,s) = Q(i1,s) or Q(i1,sx_{i}).
The total number of arithmetic operations is
 O(n(P − N)).
For example, if all the values are
 O(n^{k})
for some k, then the time required is
 O(n^{k+1}).
This solution does not count as polynomial time in complexity theory because PN is not polynomial in the size of the problem, which is the number of bits used to represent it.
Polynomial time approximation algorithm
An approximate version of the subset sum would be: given a set of N numbers x_{1}, x_{2}, ..., x_{N} and a number s, output
 yes, if there is a subset that sums up to s;
 no, if there is no subset summing up to a number between (1c)s and s for some small c>0;
 any answer, if there is a subset summing up to a number between (1c)s and s but no subset summing up to s.
If all numbers are nonnegative, the approximate subset sum is solvable in time polynomial in N and 1/c.
The solution for subset sum also provides the solution for the original subset sum problem in the case if the numbers are small (again, for nonnegative numbers). If any sum of the numbers can be specified with at most P bits, then solving the problem approximately with 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 N and 2^{P} (i.e., exponential in 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 x_{i}+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 one to another if y<(1c/N)z, set y=z and add z to S if S contains a number between (1c)s and s, output yes, otherwise no
The algorithm is polynomial time because the lists S, T and U always remain of size polynomial in N and 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 z into S if the previous y is at most
 (1 − c/N)z.
This step ensures that each element in S is smaller than the next one by at least a factor of (1 − c/N) and any list with that property is of at most polynomial size.
The algorithm is correct because each step introduces a multiplicative error of at most (1 −c/N) and N steps together introduce the error of at most
 (1 − c/N)^{N} < 1 − c.
Generalisations
Although the problem was described above in terms of integers and addition, it can actually be defined using any group. For example, the problem could be: given an integer n and a set of integers in the range [0, n − 1], does any subset sum to zero modulo n? This form of the problem has been used as a basis for several public key cryptography systems. However, most of them have been broken, reducing confidence in those still unbroken. For some reason, it is traditional in cryptography to say "knapsack problem" when it is actually the subset sum problem that is meant.
No algorithm is known for which we can prove that it solves subset sum in polynomial time. If any such algorithms exist, then some of them are already known. See the bottom of the complexity classes P and NP for one such algorithm.
References
 T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 1990. Chapter 37.4, The subsetsum problem.
External links
 An algorithm (exponential time) for solving the subset sum problem (http://www.geocities.com/SiliconValley/Garage/3323/aat/a_diop.html#diophant)
 A simple trivial solution (http://www.geocities.com/martinpintob/subsets/Subset.txt)de:Subset Sum