Given is a set of integers from 1 to $N$ (both inclusive), now I remove a number $y$ (for some $1 \leq y \leq N$) from the set $\{1, \dots ,N\}$. Now how to divide this subset into 2 subsets such that sum of both subsets is same. Where $N \leq 1000000$ (i.e. $N \leq 1\text{E}6$). Dynamic programming solution does not help. Suggestions for some linear time or $O(n\log n)$ type algorithm.
if the answer does not exist return false else print the elements of both subsets.
I think it should be possible by a fixed rule rather than a search algorithm. Suggestion: Start by splitting the set $\lbrace1, \ldots, N\rbrace$ into subsets $D$ containing the odd numbers and $E$ containing the even numbers. The next step depends on $N \mod 4$. Suppose e.g. $N = 4m + 3$ for some integer $m \ge 1$ (the case $N = 3$ is impossible, as Useless has noted). The elements of $D$ add to $4m^2 + 8m + 4$ and the elements of $E$ add to $4m^2 + 6m + 2$. So the partition when $N \equiv 3 \mod 4$ is possible only if $y$ is even, say $y = 2z$. When $y$ has been deleted from $E$, then $D$ exceeds $E$ by $2m + 2 + 2z$, so we can get a solution by transferring a total of $m + 1 + z$ from $D$ to $E$. Either $m + z + 1$ itself is in $D$, or $m + z$ is in $D$ and we can transfer it along with $1$. It should be possible to work out something similar for $N \equiv 0, 1, 2 \mod 4$. $$\ $$ Later: Here are solutions for the other cases of $N \mod 4$. $$\ $$ $N = 4m\ (m \ge 1)$. The elements of $D$ add to $4m^2$, of $E$ to $4m^2 + 2m$; $y$ must be even. Say $y = 2z$ is removed from $E$. If $z = m$, do nothing. If $1 \le z < m$, move each of $2m + 2z + 1, \ldots, 4m$ into the opposite set; that is, each is moved into $D$ if it's even, into $E$ if it's odd. If $m < z \le 2m$, move each of $2, \ldots, 2z - 2m + 1$ into the opposite set. $$\ $$ $N = 4m + 1\ (m \ge 1)$.The elements of $D$ add to $4m^2 + 4m + 1$, of $E$ to $4m^2 + 2m$; $y$ must be odd. Say $y = 2z + 1$ is removed from $D$. If $z= m$, do nothing. If $0 \le z < m$, move each of $2m + 2z + 2, \ldots, 4m + 1$ into the opposite set. If $m < z \le 2m$, move each of $1, \ldots, 2z - 2m$ into the opposite set. $$\ $$ $N = 4m + 2\ (m \ge 1)$. The elements of $D$ add to $4m^2 + 4m + 1$, of $E$ to $4m^2 + 6m + 2$; $y$ must be odd. Say $y = 2z + 1$ is removed from $D$. Let $z = 2w$ if even, $2w + 1$ if odd. If $m$ is even, move $m + 2w + 2$ from $E$ to $D$; and if also $z$ is even, move $2$ to $D$ and $3$ to $E$. If $m$ is odd, move $m + 2w + 1$ from $E$ to $D$, and if also $z$ is odd, move $1$ to $E$ and $2$ to $D$.