Partition problem asks whether it is possible to partition some multiset $S$ into two sets such that their sums are equal.
Applying the computational solution, it seems that if $S$ contains each integer from $1$ to $n$ exactly once, then this is possible if and only if $n+1\equiv 0,1 \pmod 4$. It is clear that this is a necessary condition (total sum of $S$ must be even).
To prove that this is also a sufficient condition, the same proof as to Multisets that can be partitioned into two sets of equal sum applies here. (We need to find a subset that sums to half of the total sum of $S$, and every sum between $1$ and $\sum S$ is possible.)
Here comes the twist. When observing the sorted elements with their signs $\pm1\pm2\pm3\pm\dots\pm n=0$, it is required that at each step, the result is non-negative.
For example, if $S=S_+\cup S_-$ then it must be $1,2\in S_+$ because otherwise we would have $-1\lt 0$ and $1-2\lt 0$, negative steps. Then $3$ can be in either set, but if $3\in S_-$ then $4$ can't be in $S_-$ as it would be $1+2-3-4\lt 0$ a negative step, etc.
It seems that with this additional constrain, $n+1\in\{5,8\}$ become impossible.
My question is, are these two numbers the only numbers that become impossible? If not, can we find all numbers that now become impossible?
I'm assuming you mean that the sums are always nonnegative, as you allow $1+2-3+4+\cdots$.
Construct $S_-$ greedily by starting with $S_-=\emptyset$ and, at each step, adding the largest number that is not yet in $S_-$ and doesn't cause the sum of elements in $S_-$ to be greater than $\frac{n(n+1)}4$. This process will add $n$ to $S_-$, then $n-1$, etc. up through $n-k$, pausing when $$n+(n-1)+\cdots+(n-k)+(n-k-1)>\frac{n(n+1)}4.$$ If $n+(n-1)+\cdots+(n-k)=n(n+1)/4$, then we're done; otherwise, the process then adds $$0<\frac{n(n+1)}4-\big(n+(n-1)+\cdots+(n-k)\big)<n-k-1$$ and terminates. The only way this fails to produce a partition with the desired property is if $$\frac{n(n+1)}4-\big(n+(n-1)+\cdots+(n-k)\big)\in\{1,2\}.$$ In these "bad" cases, we modify the partition slightly. If $$S_-=\{1,n-k,n-k+1,\dots,n\},$$ instead use $$S_-'=\{3,n-k-1,n-k,n-k+2,\dots,n\},$$ i.e. replace $1$ and $n-k+1$ with $3$ and $n-k-1$. This works as long as $n-k-1\geq 7$ and $k\geq 2$, which holds as long as $n\geq 9$.
If $$S_-=\{2,n-k,n-k+1,\dots,n\},$$ instead use $$S_-'=\{3,n-k-1,n-k+1,\dots,n\}.$$ This works as long as $n-k-1\geq 6$, which holds for $n\geq 8$.
So, the only remaining cases are $n\in\{3,4,7,8\}$. Since $$1+2-3=0,\qquad 1+2-3+4+5+6-7-8=0,$$ and you have argued that $n=4$ and $n=7$ fail, this shows that all $n\equiv 0,3\pmod 4$ besides $4$ and $7$ work.