-1
$\begingroup$

what is a general algorithm to compute if a set have nonempty integer subset that have integers add up to 0?

i would like to know one with the least tries and the proof of it.

Example:{−2, −3, 15, 14, 7, −10} have integers added up to zeros since {−2, −3, −10, 15} add up to zero

i would also like to know the level of it - undergraduate or graduate?

  • 3
    @Victor: What "computer language" are you talking about? The only remotely computerlike notation in the Wikipedia article is a block of high-level _pseudocode_. If you cannot read _that_, you shouldn't be trying to understand algorithms.2012-07-11

1 Answers 1

1

This is the well known subset sum problem, and there is an $O\left ((\sum x_i) ^2\right )$ dynamic programming (based on a recurrence relation) algorithm. Wikipedia has a nice explanation of it here: http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

What do you mean when you ask for the algorithm with the "least tries"? If you mean runtime, this algorithm is the fastest.

Regarding the level, a student in an introductory computer science course should be able to devise a solution of this kind.