Any way to determine if a finite multiset of natural numbers can be combined via addition or subtraction to form zero? Disclaimer: I studied math at college, but it was decades ago; my current level is "idiot," and my question is probably about a well-known problem. However, I've tried extensive web searches, to no avail. Any help is appreciated!
For a game I'm developing, I need to generate/evaluate small multisets of natural numbers that can be combined via addition/subtraction to form zero.
For instance, $\{3, 2, 2, 1\}$ is such a multiset since e.g. $3 - 2 - 2 + 1 = 0$. But $\{3,1\}$ is obviously not compliant with the requirement.
In other words, I need to work with finite multiset of $\{x_1, x_2, ..., x_n\}$ where each $x_i$ is a natural number, for which there exists a multiset of coefficients $\{S_1, S_2,..., S_n\}$ where $S_i \in \{{-1}, {+1}\}$ so that $S_1x_1 + S_2x_2 + ... + S_nx_n = 0$.
I'm not interested in the coefficients, just need to find a way to evaluate if a multiset complies with this rule without trying all the $2^n$ possibilities. Also, if this rule can be substituted for something simpler, I could use it when generating such sets.
Quite clearly the sum of all the numbers in the set needs to be even, but that's not enough (see counterexample above).
Also, no number must be greater than the sum of all the other numbers in the multiset, but that's not sufficient either since $\{5,5,1,3\}$ doesn't seem to have a solution.
First I thought it may be a special case because of the duplicate (see below why it's not). The duplicate may be replaced by either 0 or its double: for the former, a multiset such as $\{5,5,1,2,3\}$ has a solution since $\{1,2,3\}$ does, and for the latter, $\{5,5,8,1,1\}$ can form zero since $\{10,8,1,1\}$ can. Both of these examples comply with the "no member greater than sum of all the rest" requirement after the elimination of the duplicate, so this may be a lead after all.
Edit: well, it's not just because of the duplicate, since $\{100,99,3\}$ does initially comply with the "no single member too great" requirement, but still isn't solvable. So it seems that the "no single member too great" requirement must be maintained after each step, but I really don't know what to do with that…
This is how far I've got on my own. I hope there's much more out there. Thanks a lot for any pointers on this!
 A: This is an NP-complete problem, equivalent to the Subset-sum problem.
If $T$ is the sum of all your numbers $x_n$, your problem is equivalent to finding
a subset whose sum is $T/2$. Given such a subset, you give the members of that subset
the sign $-$ and the others the sign $+$.
Thus there is no known polynomial-time algorithm, but there is a pseudo-polynomial time dynamical programming algorithm.  It goes like this.
Suppose your numbers are $x_1, \ldots, x_n$ (assumed to be positive integers).  For
integers $1 \le m \le n$ and $0 \le t \le T/2$, let $I(m,t) = 1$ if there is a subset
of $x_1, \ldots, x_m$ whose sum is $t$, and $0$ if not.  You compute it as follows.
Start with $I(1,0) = 1$, $I(1,x_1) = 1$, all others $0$.  Then given the $I(m,t)$,
$I(m+1,t) = 1$ if either $I(m,t) = 1$ or ($t \ge x_{m+1}$ and $I(m,t-x_{m+1}) = 1$).
The answer to your problem is yes if and only if $I(n,T/2) = 1$ (of course $T/2$ must be on integer, so $T$ must be even).
A: Your example of the multiset $\{5,5,1,3\}$ made me think that it should be possible to solve the problem recursively: Take the two $5$s in the multiset. They either have different signs in the sum, in which case they cancel each other out, or they have the same sign, in which case they can be replaced by a single $10$.
Therefore, your multiset has a solution if and only if at least one of the multisets $\{1,3\}$ or $\{10,1,3\}$ does. However, none of these derived multisets has a solution due to your "no number must be greater than the sum of all the others" rule.
You can probably spend quite a bit of time to try and come up with a variant of this algorithm which has acceptable complexity, but I agree with you: There must be some work on this already.
