Is subset sum problem with multiplicities NP-complete?
The problem can be solved in polynomial time.

If any of the $a_i$ are zero, then the answer is "yes" (you can set the corresponding $x_i$ to 1, and all other $x_j$ to 0).  So let's assume all of the $a_i$ are non-zero.

If all of the $a_i$ are strictly positive, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i&gt;0$ and $a_i&gt;0$, so $a_1 x_1 + \dots + a_n x_n \ge a_i x_i &gt; 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If all of the $a_i$ are strictly negative, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i&gt;0$ and $a_i&lt;0$, so $a_1 x_1 + \dots + a_n x_n \le a_i x_i &lt; 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If at least one of the $a_i$ is strictly positive and at least one is strictly negative, say $a_i&gt;0$ and $a_j&lt;0$, then the answer is "yes" (you can take $x_i=-a_j$, $x_j=a_i$, and set all other $x$'s to zero; then $a_1 x_1 + \dots + a_n x_n = a_i x_i + a_j x_j = -a_i a_j + a_i a_j = 0$).

These cases cover all the possibilities: at least one of the above cases must hold.  So, we obtain a polynomial-time algorithm for the original problem.

Credit: I got the key idea from Discrete lizard.