Partition problem for first $n$ consecutive integers, but with a twist 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?
 A: 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.
