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$.
 A: To start with, you can forget about the leading term, $1$.
All that term does is to shift all the values one place to the right
on the number line.
The expression $\pm 2 \pm 3 \pm \cdots \pm n$
has the same number of distinct values as $1 \pm 2 \pm 3 \pm \cdots \pm n$.
From this point until further notice, I'll consider only sums of
the form $\pm 2 \pm 3 \pm \cdots \pm n$.
All possible sums have the same parity.
The minimum sum is $\sum_{i=2}^n(-i) = -\frac{(n+2)(n-1)}{2}$, 
when all the $\pm$ signs
are negative. The sum $-\frac{(n+2)(n-1)}{2} + 2$
is clearly not achievable, but $-\frac{(n+2)(n-1)}{2} + 4$ is,
as long as $n \geq 2$.
Now as long as the sum includes two terms $j - (j+1)$ 
(positive followed by negative), we can change the two terms to
$-j + (j+1)$ and thereby increase the sum by $2$.
If there are no such terms, that is, all the negative terms occur
before any of the positive terms, the sum has the form
$$-2 - 3 - \ldots - (j-1) - j + (j+1) + \ldots + n = k \tag1$$
where $1 \leq j \leq n$. (In the case $j = 1$, all terms are positive.)
We have already considered the case $j = n$.
In the case $j=1$, the sum has the maximum value, 
$\frac{(n+2)(n-1)}{2}$,
and in the case $j=2$, the sum has the second greatest possible value,
$\frac{(n+2)(n-1)}{2} - 4$.
Now suppose instead that $3 \leq j \leq n-1$.
Then we can change the sum on line $(1)$ to
$$2 - 3 - \ldots - (j-1) + j - (j+1) + \ldots + n = k + 2.$$
In other words, if $n > 3$, then except for the values 
$-\frac{(n+2)(n-1)}{2}$,
$\frac{(n+2)(n-1)}{2} - 4$, and $\frac{(n+2)(n-1)}{2}$,
every possible value of the sum 
(including $-\frac{(n+2)(n-1)}{2} + 4$) 
corresponds to another sum that is greater by $2$.
So the possible sums are $-\frac{(n+2)(n-1)}{2}$, $\frac{(n+2)(n-1)}{2}$,
and every integer of the same parity from $-\frac{(n+2)(n-1)}{2} + 4$
to $\frac{(n+2)(n-1)}{2} - 4$, inclusive.
The number of integers in 
$\left[-\frac{(n+2)(n-1)}{2}, \frac{(n+2)(n-1)}{2}\right]$
is $(n+2)(n-1) + 1$, and those of the same parity are 
$\frac{(n+2)(n-1)}{2} + 1$.
So if $n > 3$, the total number of possible sums (excluding the
values $-\frac{(n+2)(n-1)}{2}+2$ and $\frac{(n+2)(n-1)}{2}-2$, 
which are not possible sums) is 
$$\left(\frac{(n+2)(n-1)}{2} + 1\right) - 2 = \frac12(n^2 + n - 4).$$
For example, if $n=4$ then there are $8$ possible sums:
$-9,-5,-3,-1,1,3,5$, and $9$.
By inspection, this formula also gives the number of sums for $n=3$
(the sums are $-5,-1,1,$ and $5$),
but the number of sums for $n=2$ is $2$, which does not agree with
the formula; $n=2$ must be treated as a special case.

If you modify the original expression by making the first term $\pm1$,
that is, if you consider $\pm 1 \pm 2 \pm \cdots \pm n$,
the minimum is $-\frac{n(n+1)}{2}$,
the maximum is $\frac{n(n+1)}{2}$,
and all integers of the same parity between those values are
possible sums.
A: Let us use generating functions
$$G_n(X)=X\prod_{k=2}^n(X^{-k}+X^k)=\dfrac{1}{X^p}\prod_{k=2}^n(1+X^{2k}) \ \ \ \text{with} \ \ \ p=\frac{n(n+1)}{2}-2$$
(very close to the proposal of @Jack D'Aurizio). In this way, we transfer the issue into counting how many combinations as positive or negative exponents of indeterminate $X$ are present in the expansion of $G_n(X)$.
Let us manipulate the first values of $n$ which is enough to get a good perception of the method. 
We begin by the case  $n=3$: 
$$G_3(X)=X(X^{-2} + X^2)(X^{-3} + X^3)=$$
$$X^{1-2-3} + X^{1+2-3} + X^{1-2+3} +X^{1+2+3}$$
$$=X^{-4} + X^0 + X^2 + X^6$$
Note the central symmetry (with respect to position $1$) of the exponents $-4,0,2,6$. This central symmetry will exist for all values of $n$.
Let us now consider the cases $n=4, 5, 6$:
$n=4$:
$$G_4(X)=X(X^{-2} + X^2)(X^{-3} + X^3)(X^{-4} + X^4) =$$
$$X^{-8} + X^{-4} + X^{-2} + X^0+ X^2 + X^4 + X^6 + X^{10}$$
Till now, there are no repetitions. Here they come for $n \geq 5$:
$n=5$:
$$G_5(X)=X(X^{-2} + X^2)(X^{-3} + X^3)(X^{-4} + X^4)(X^{-5} + X^5)$$
$$=X^{-13} + X^{-9} + X^{-7} + X^{-5} + 2X^{-3} + 
  X^{-1} + 2\,X + X^3 + 2\,X^5 + X^7 + X^9 + X^{11} + 
  X^{15}$$
This time, not all coefficients are one; the reason is clear: for example, monomial $^2X^5$ means that $5$ is obtainable in two ways, i.e., $1+2+3+4-5$ and $1-2-3+4+5$. This is an "added value" of the approach by generating functions.
A last case, $n=6$, in order to see the differences between the cases $n$ odd and $n$ even:
$$X(X^{-2} + X^2) \cdots (X^{-5} + X^5)(X^{-6} + X^6)=$$
$$=X^{-19} + X^{-15} + X^{-13} + X^{-11} + 2X^{-9} + 
  2X^{-7} + 2X^{-5} + 2X^{-3} + 
  3X^{-1} + 2\,X + 3\,X^3 + 2\,X^5 + 2\,X^7 + 2\,X^9 + 
  2\,X^{11} + X^{13} + X^{15} + X^{17} + X^{21}$$
I will not go beyond this point because there is a clear recurrence relationship, but developing it would look to the reader like paraphrasing the (very detailed) redaction of @David K .
A: 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?
A: In a similar, but newer question here in MSE I gave a "proof without words" (however, I needed a couple of words to explain the picture).       
Here is a similar picture; if you have read the explanations in that other thread once, you never need this anymore...

It means, we begin with the set-of-result $R_0 = \{0\}$ having cardinality $ \# R_0=1$ .            
Then we initialize a set of summands, $S_1=\{1\}$ . To each element in $R_0$ we add the new summand $s_1=1$ getting a new results-set $R_1 = \{1\}$. Its cardinality is $\#R_1=1$ . In the picture this is reflected by the top-most green arrow for addition; because we do not use $-1$ the subtraction-arrow is grey and the subtraction-value $-1$ is not a valid element in  $R_1$       
After that we add the element $s_2=2$ to our summands-set. We arrive at the new results-set $R_2$ by adding (green arrows) and subtracting (red arrows) that $s_2$ to each element in $R_1$.       
And so on. 
In the picture I've documented in grey the missing elements compared with the symmetric tree, when the first summand were $ \pm 1$ in the problem definition instead of only $+1$ .        
But the evolution of the iteration becomes immediately clear after seeing $R_4$ and $R_5$. In each new row shall 3 elements be invalid/missing compared with the symmetric tree as shown in the other answer. The formula for the cardinalities can simply be derived to be (for $ k \ge 3$): 
$$ \# R_k = \binom{1+k}{2} -2 $$
