This is one of those problems where you either see it or you don't. The crucial claim is that \[ (S_n-S_{n-2}+S_{n-4}-...)^2+(S_{n-1}-S_{n-3}+S_{n-5}-...)^2 = \prod_{j=1}^n (a_j^2 + 1) \geq \prod_{j=1}^n (2a_j) = 2^n S_n. \]To see this, let $P(x) = (x-a_1)(x-a_2)\cdots (x-a_n)$ and note that the expression on the left hand side is $|P(i)|^2$. Thus $a_j^2 + 1 = 2a_j$ for all $j$, i.e. $a_j = 1$ for all $j$.

djmathman wrote: Thus $a_j^2 + 1 = 2a_j$ for all $j$, i.e. $a_j = 1$ for all $j$. Actually $a_j^2+1=2|a_j|$, for all $j$. For equality there must be an even number of $-1$s, so the first $n-1$ numbers can be chosen randomly to be $-1$ or $1$, and the last one is uniquely determined by them. Hence, there are $2^{n-1}$ solutions.