Given a set $U=\{1,2,3,...n\}$. How to partition elements in $U$ into sets $A$ and $B$ such that the sum of the elements in $A$ and $B$ is in minimum. I came across a particular problem wherein I think the answer would necessitate me to partition $U=\{1,2,3,...n\}$ into subsets $A$ and $B$ such that the sum of the elements in $A,B$ is at minimum.
To show that it is in minimum, the following should hold:
Let:
$sumA$ be the sum of the elements in $A$
$sumB$ be the sum of the elements in $B$
Then $sumA,sumB$ is at $minimum$ when $|sumA-sumB|$ is at $minimum$.
Possible Cases:
We are actually looking for all subsets of $U$. The number of subsets of $U$ is $2^n$.
Example: Let $U$={1,2,}. Then the number of subsets are $2^2=4$:
$\{1,2\}$,$\{1\}$,$\{2\}$,$\{\}$
We will drop  $\{1,2\}$,$\{\}$ since they irrelevant to our task. So there should be $2^n-2$ possible subsets to be paired, in this case $\{1\}$,$\{2\}$.
Let $p$ be the possible subsets, then:
$$p=2^n-2$$
The number of ways to arrange these subsets into $2$ sets is $p\cdot\ (p-1)=2^n-2 \cdot\ (2^n-3)$.
Problem: My problem is to figure out what will be the exact combination of subsets $A,B$ such that $sumA$ and $sumB$ is at the minimum. Any help would be very helpful.
 A: Split them into consecutive groups of $4$ starting with the largest ( so the first block is $\{n-3,n-2,n-1,n\}$ ) and in each group $\{a,a+1,a+2,a+3\}$ split them so  $a$ and $a+3$ are in $A$ and $a+1$ and $a+2$ are in $B$.
If the number of elements is a multiple of $4$ we are done.
If the remainder is $1$ put $1$ in $A$.
If the remainder is $2$ put $1$ in $A$ and $2$ in $B$.
If the remainder is $3$ put $1$ and $2$ in $A$ and $3$ in $B$.
It is not hard to see this is optimal.
A: Using your notation we immediately see that sumA + sumB = sumU.  Ideally, we want sumA = sumB because then both are minimum.  There are numerous ways of doing this, so here is one way.  Set R = n mod 4.  If n is divisible by 4 then R is zero.  Otherwise, R is either 1, 2, or 3.  Now consider the set {R+1, R+2, R+3, … n-1, n}.  We can pair these up by matching the first and last and placing alternate pairs in set A and set B.  This will give identical sums in both sets of (n+R)(n+R+1)/4 for each set.  This leaves us with the first R elements which also need to be allocated.  There are four cases to consider:
R = 0 - nothing left to allocate
R = 1 - place the remaining "1" in either set and the difference is just 1
R = 2 - place the remaining "1" in one set and the "2" in the other set and the difference is still only 1.
R = 3 - place "1" and "2" in one set and "3" in the other set and both sums are the same.
