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
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(n) denote the
n-th element in current list.
While list has more than one element,
SUM + a(1)or
SUM - a(1), whichever is closest to
a(2). (where closest means
|a(2) - SUM_POSSIBLE|is minimum).
a(1), there exists a linear sum.
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