Is there a way to check whether a set containing 1 to n integers can be partitioned in 2 equal sum subsets in minimum time complexity.


closed as off-topic by Aqua, GNUSupporter 8964民主女神 地下教會, ahulpke, Morgan Rodgers, hardmath Jan 8 '18 at 0:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Aqua, GNUSupporter 8964民主女神 地下教會, ahulpke, Morgan Rodgers, hardmath
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ If $n$ is divisible by $4$, you can do it for sure. $\endgroup$ – AlexanderJ93 Jan 7 '18 at 20:15
  • 1
    $\begingroup$ Are you asking about the set $\{1,2,3,\ldots,n\}$, or about arbitrary sets of $n$ integers? $\endgroup$ – Barry Cipra Jan 7 '18 at 21:07
  • $\begingroup$ It would improve your Question (and clarify it) if you worked out a couple of small examples to include in the body of your Question. E.g. $\{1,2,3\}$ can be partitioned into two equal sum subsets, but no proper subset of it (except the empty set) can be so partitioned. $\endgroup$ – hardmath Jan 8 '18 at 0:32

Yes, it is possible if and only if $n\equiv 0,3\pmod 4$.

Because $1+2+\cdots+n=\frac{n(n+1)}{2}$, for this to be further divisible by $2$ we must have either $n$ or $n+1$ divisible by $4$, which means $n\equiv 0,3\pmod 4$.

Conversely, assume $n\equiv 0,3\pmod 4$. It is obvious that four consecutive numbers can be split into pairs giving the same sum. ($\{k,k+1,k+2,k+3\}$ can be split into $\{k+1,k+2\}$ and $\{k,k+3\}$, both giving sum $2k+3$.) Now, start taking groups of $4$ numbers off the end of the sequence $1,2,\ldots,n$ (last $4$ numbers, then the $4$ numbers before that, then the $4$ numbers before that etc.). Split those as shown above. What you end up at the end is:

  • $n\equiv 0\pmod 4$: nothing. We've thus split the whole set into two sets with equal sums.
  • $n\equiv 3\pmod 4$: remaining are $\{1,2,3\}$, which can be split into $\{1,2\}$ and $\{3\}$.

Examples for those two cases:

  • $n=8$: $8+5+4+1=7+6+3+2$
  • $n=11$: $11+8+7+4+3=10+9+6+5+2+1$