How many values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take? 
How many different values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take?

I was wondering about this problem and didn't think it was immediately obvious. The answer can't be $2^{n-1}$ since the combinations all might not be unique. I was thinking of looking at partitions of $\{1,2,\ldots,n, k\}$ where $1 \pm 2 \pm 3 \pm \cdots \pm n = k$ and thus the sum must be even. Therefore, $\dfrac{n(n+1)}{2}+k = \dfrac{n(n+1)+2k}{2}$ must be even which means $n(n+1) + 2k$ must be a multiple of $4$ so $n(n+1)+2k = 4m$. Thus if $n \equiv 1,2 \bmod 4$, then $k \equiv 1,3 \bmod 4$ and if $n \equiv 3,0 \bmod 4$ then $k \equiv 0,2 \bmod 4$.

Hint:
$$ 1\pm 2\pm 3\pm 4\ldots \pm n = \frac{n(n+1)}{2}-a_2-a_3-\ldots-a_n, \qquad a_k\in\{0,2k\}.$$
Consider $(1+x^4)(1+x^6)\cdot\ldots\cdot(1+x^{2n})$. How many monomials appear in the expansion?
