Equal partition up to one integer
There is an $O(n \log n)$ algorithm for this problem.

To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that $|\sum_A - \sum_B| \le M$.

Start by putting the $a$ largest integers into $A$ and the $b$ smallest to $B$. Now, if $\sum_A &lt; \sum_B - M$, there is no solution because we cannot make the sum of $A$ any larger. If $\sum_B - M \le \sum_A \le \sum_B + M$, the partition $(A, B)$ is a solution and we are ready. The case that is left is $\sum_B + M &lt; \sum_A$. In this case, we can repeatedly choose the largest element of $A$ and the smallest element of $B$ and swap them. The difference $\sum_A - \sum_B$ changes by at most $2M$, so either we find a solution or maintain the invariant $\sum_B + M &lt; \sum_A$. At some point we must find a solution, because $a$ is smaller than $b$, and thus $\sum_A$ will become smaller than $\sum_B$ by repeating this operation.
This can be implemented in $O(n \log n)$ with sorting and two pointers.