The problem of finding a maximum cardinality discrepancy partition (or determining that one doesn't exist) is solvable in pseudo-polynomial time even if a balanced partition is not given.
Suppose that the input is a multiset of positive integers $S = \{x_1, \ldots, x_N\}$. Let $K = \sum_{i = 1}^Nx_i$. Below I demonstrate a dynamic programming algorithm for finding a maximum cardinality discrepancy partition of $S$.
Suppose $s$, $i$, and $c$ are variables with $0 \le s \le K$ and $0 \le c \le i \le N$. Then define $p(s, i, c)$ to be true if and only if there exists a multiset $T \subseteq \{x_1, \ldots, x_i\}$ whose cardinality is $c$ and whose sum is $s$.
We can define a recurrence:
- $p(s, 0, 0)$ is true iff $s = 0$.
- $p(s, i, c)$ is true if either $p(s, i-1, c)$ or $p(s - x_i, i-1, c-1)$ is true.
- $p(s, i, c)$ is false otherwise.
Using this recurrence we can compute the value of $p$ on all valid $s$, $i$, and $c$ in time polynomial in $N$ and $K$.
Furthermore, the predicate $\phi(c) = p(\frac{K}{2}, N, c)$ can be interpreted as "does there exist a subset of $S$ of cardinality $c$ whose sum is half of the sum of $S$?" or equivalently as "does there exist a partition of $S$ with cardinality discrepancy $|N-2c|$?". Thus, after finding all the values of $p$, we can simply look through all the values of $\phi(c) = p(\frac{K}{2}, N, c)$ and select the value of $c$ with $\phi(c)$ true for which the cardinality discrepancy $|N-2c|$ is largest. Call this value $c_0$. If $\phi(c)$ is never true then there is no partition of $S$.
All that's left is to actually find the partition of $S$ one of whose sets has size $c_0$. Here's an algorithm for doing this:
initialize P_1 and P_2 to be empty lists
initialize (s, c) to (k/2, c_0)
for i = N, N-1, ..., 1
| if p(s, i-1, c) is true:
| | add x_i to P_1
| else:
| | add x_i to P_2
| | set (s, c) to (s - x_i, c-1)
output P_1 and P_2
Notice that this algorithm is just following the recurrence of $p$ back from $p(\frac{K}{2}, N, c_0)$ to $p(0,0,0)$. That is, the algorithm maintains the invariant that $p(s, i, c)$ is always true at the start of the loop (this is easy to prove by induction). The invariant even continues to hold after the last iteration of the loop; that is, $p(s, 0, c)$ is true after the loop. Since $p(s, 0, c)$ is only true if $s = c = 0$, we can deduce that $s$ and $c$ decrease from $\frac{K}{2}$ and $c_0$ to $0$ over the course of a loop. Looking at the only line where $s$ and $c$ change, this clearly implies that list $P_2$ ends up containing exactly $c_0$ elements whose total sum is $\frac{K}{2}$. In other words, $P_1$ and $P_2$ form a partition of $S$ whose cardinality discrepancy is $|N - 2c_0|$, which by definition of $c_0$ is exactly the largest possible cardinality discrepancy for any partition of $S$.
