# Partitioning integer with subtraction allowed

Let's imagine you want to get a number $$A$$ from a set of number $$M$$. You might use only +/- between the numbers and your job is to determine, whether it's possible to get the result $$A$$ or not.

So let's say $$A = 12$$ and $$M =\{ 3,4,5 \}$$ then the solution is $$3+4+5 = 12$$. $$-3-4-5 = -12$$ so $$-12 <= A <= 12$$.

The number of possible ways is $$2^n$$ where $$n$$ is number of elements in $$M$$. I also know that if there is odd number of odd numbers, $$A$$ must be odd and the GCD of $$M$$ must be also denominator of $$A$$ and so on. But in case I'm given $$100$$ numbers, it's not possible to check every possible way.

With two numbers, like $$M = \{ 3, 4 \}$$, solving it for let's say $$A = 1$$ might be as simple as solving two variable equations:

$$x^2 + y^2 = 25$$

$$x + y = 1.$$

But with $$3$$ or more numbers, it's just two equations and many variables. Is there a way to determine, if $$A$$ is among those possibilities ?

• Can we use the operation +- on the same numbers several times ? ie for $M = \{ 3,4\}$ can I take $9 = 3 + 3 + 3$ or $k 3 = 3 + ... + 3$ ($k$ times ) ? – Digitalis Feb 20 at 13:29
• @Digitalis No. Every number from M has to be used exactly once. – ShinobiUltra Feb 20 at 13:34
• Exactly once ? Take $M = \{ 3, 4\}$ so $3$ is not valid ?!? – Digitalis Feb 20 at 13:45
• @Digitalis sorry for late answer; no, you cannot get 3 by using 3 and 4. Only 7, -7 and 1, -1 (3+4, 3-4, -3+4, -3-4), nothing else. – ShinobiUltra Feb 20 at 21:55