Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
en.wikipedia.org/wiki/Subset_sum_problem - this problem is believed to be 'hard' (it's NP-complete), and many algorithms are known for it. –  Steven Stadnicki Jul 11 '12 at 0:48
    
@StevenStadnicki - i can't read the computer langauage, may someone put those algorithm in english and math langauage? –  Victor Jul 11 '12 at 0:51
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. –  Henning Makholm Jul 11 '12 at 0:56

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.