Find sum in array equal to zero

Given an array of integers, find a set of at least one integer which sums to 0.

For example, given [-1, 8, 6, 7, 2, 1,开发者_如何学运维 -2, -5], the algorithm may output [-1, 6, 2, -2, -5] because this is a subset of the input array, which sums to 0.

The solution must run in polynomial time.

You'll have a hard time doing this in polynomial time, as the problem is known as the Subset sum problem, and is known to be NP-complete.

If you do find a polynomial solution, though, you'll have solved the "P = NP?" problem, which will make you quite rich.

The closest you get to a known polynomial solution is an approximation, such as the one listed on Wikipedia, which will try to get you an answer with a sum close to, but not necessarily equal to, 0.

This is a Subset sum problem, It's NP-Compelete but there is pseudo polynomial time algorithm for it. see wiki.

The problem can be solved in polynomial if the sum of items in set is polynomially related to number of items, from wiki:

The problem can be solved as follows using dynamic programming. Suppose the sequence is

x1, ..., xn

and we wish to determine if there is a nonempty 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 is a nonempty subset of x1, ..., xi which sums to s".

Thus, the solution to the problem is the value of Q(n,0).

Clearly, Q(i,s) = false if s < N or s

P so these values do not need to be stored or computed. 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. Initially, for N ≤ s ≤ P, set

Q(1,s) := (x1 = s).

Then, for i = 2, …, n, set

Q(i,s) := Q(i − 1,s) or (xi = s) or Q(i − 1,s − xi)   for N ≤ s ≤ P.

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 − xi) = false if s − xi < N or s − xi > P. Therefore, the total number of arithmetic operations is O(n(P − N)). For example, if all the values are O(nk) for some k, then the time required is O(nk+2).

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

This solution does not count as polynomial time in complexity theory because P − N 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 N and P, which are exponential in their numbers of bits.

A more general problem asks for a subset summing to a specified value (not necessarily 0). It can be solved by a simple modification of the algorithm above. For the case that each xi is positive and bounded by the same constant, Pisinger found a linear time algorithm.[2]

It is well known Subset sum problem which NP-complete problem.

If you are interested in algorithms then most probably you are math enthusiast that I advise you look at

• Subset Sum problem in mathworld

and here you can find the algorithm for it

• Polynomial time approximation algorithm

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 one to another if y<(1-c/N)z, set y=z and add z to S

if S contains a number between (1-c)s and s, output yes, otherwise no