Let p(n) be the number of unrestricted partitions of n. p(0) is taken to be 1.
Let set 1 and set 2 be two empty sets.


Here's an algorithm. Put p(n) into set 1. On each successive step, k=1,2,3,..., n, put p(n-k) into that set which has the smaller sum of elements, or into set 1 if the two sets have equal sums. 


After the algorithm has ended will the sum of elements in set 1 always differ from the sum of elements in set 2 by at most 1?


I've checked for n<= 200 and this has always been the case.



Will this greedy algorithm always work?
Let a nondecreasing sequence (we'll say of positive integers) $a\_n$ starting from $a\_1=1$
be subdoubling if for all $n>2$ it satisfies the relation 
$a\_n <= 2\*a\_{n-1}$. Let $d$ be an integer with $-a\_n \leq d \leq a\_n$ and put $d$ in set 2, then run your algorithm. I claim at the
finish of the algorithm the difference between the sums is at most $a\_1=1$.


Proof Sketch: at the start the difference between the two sums is $\left| d \right| \leq a\_n$.  

Because of the subdoubling property, the difference when $a\_{n-1}$ is added at most 
$a\_{n-1}$. End of Proof Sketch.


Corollary: Given $-2\*a\_n\leq d \leq 2\*a\_n$, you can choose coefficients $\epsilon\_i$
from $\{-1,+1\}$ so that $\sum\_i \epsilon\_i \* a\_i$ is within one of $d$.


If I recall correctly, your sequence $a\_n$ is subdoubling. So you will end up with 1 even if
you pad set 2 with a small enough value.


I used something like this for the determinant spectrum problem for $0-1$ matrices.


Gerhard "Ah, The Good Old Days" Paseman, 2016.08.27


