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!
Best Answer
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).