This will be a simple problem on paper, but the brute force method is not really suitable for a computer, so I'm after a tricky algorithm that works in practice too: if $n$ positive half-integers $p\_i$ are given, one can form $2^n$ linear combinations with coefficients $\pm 1$:


$$P = e\_1 p\_1 + \ldots + e\_n p\_n$$


Where $e\_i = \pm 1$. With given $p\_i$ one obtains $2^n$ values for $P$. Let's call $\mu(P)$ the multiplicity of $P$, the number of linear combinations that gives $P$. My goal is to know this $\mu(P)$. On a computer I could just loop over $2^n$ items given by n-length strings of +1 and -1's and record each $P$, but if $n$ is large ($n>64$) this becomes problematic if 64 bit integers are used (unsigned long long int in C). And also it becomes time consumong if $n$ is larger than 64 and some arbitrary precision library is used.


Is there a tricky way to obtain $\mu(P)$ that does not require a loop over $2^n$ elements?



All possible linear combinations of positive half-integers with coefficients +/- 1
Indeed it is the Subset Sum Problem (or closely related to it). This problem asks essentially whether $\mu(P)>0$.
It is only weakly NP-complete, and there is a pseudopolynomial dynamic-programming
algorithm for it. You can find it in any textbook on algorithm design.
More precisely, if the sum of the $p\_i$'s is $B$, you can solve it in $O(nB)$ time.
Whether this is practical depends on the size of the numbers. (The other suggested solutions, which multiply polynomials, are another way to express the same algorithm. Your question suggests that $\mu(P)$ is not just 0 or 1, and apparently, the numbers are not so big.)


