Algorithm to check for a linear sum to zero

2
votes

Given a list of N non-negative integers, propose an algorithm to check if the sum of X numbers from the list equals the remaining N-X.

In other words, a simpler case of the Subset sum problem which involves the entire set.

An attempted solution

Sort the elements of the list in descending order. Initialize a variable SUM to the first element. Remove first element (largest, a(1)). Let a(n) denote the n-th element in current list.

While list has more than one element,

  1. Make SUM equal to SUM + a(1) or SUM - a(1), whichever is closest to a(2). (where closest means |a(2) - SUM_POSSIBLE| is minimum).

  2. Remove a(1).

If the SUM equals -a(1) or a(1), there exists a linear sum.

The problem

I cannot seem to resolve above algorithm, if it is correct, I would like a proof. If it is wrong (more likely), is there a way to get this done in linear time?

PS: If I'm doing something wrong please forgive :S

1
algorithmsubset-sum

1 Answers

1
votes

Notice that you want the sum of x numbers to be equal to the sum of the other N-x numbers.
You can simplify this by saying you want to see if there's a subset which sums up to S/2 where S is the total sum of the whole set.

So, you can calculate the Sum you need to get to with one iteration (O(n)).

Then just use a known algorithm like Knapsack to find a subset that meets your sum.

Another more "mathematical" explanation: Dynamic Programming – 3 : Subset Sum

Edit:

As an answer to your other question, your algorithm is wrong. consider this list of numbers:

{3,3,4,4}

The total sum is 14, so you're looking for a subset with the sum of 7. Obviously it will be 3+4.

Your algorithm will return false after examining the 2 3's