I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or differ only by 1 (if n is odd).
I think we can do this in pseudo polynomial time $O(n^2 A)$, where $A$ is the sum of numbers in the set.
Can I do better than this? Namely, is there a pseudo polynomial time algorithm that runs in time $O(n^c A)$ with $c < 2$?
Thanks in advance!
One can solve the decision problem in $\tilde{O}(nA)$ time.
Let the sequence of numbers be $S$. Define $F_S$ to be a set such that $(i,j)\in F_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F_S$, then we just need $O(nA)$ additional time to go thorough $F_S$ to solve your problem.
If $S_1$ and $S_2$ are two subsequences that partitions $S$, then
$$F_S = F_{S_1} + F_{S_2}$$
where $A+B=\{a+b | a\in A, b\in B\}$ is the minkowski sum, and addition between tuples are defined coordinate-wise.
Claim: Computing $F_S$ from $F_{S_1}$ and $F_{S_2}$ takes $\tilde{O}(|S|A)$ time.
Proof: Apply 2D convolution on two tables of size $A\times |S|$.
The algorithm partition the sequence to two equal sized sequences, apply recursion to each, and take the minkowski sum of the result. Let $T_A(n)$ be the worst case running time when the input to the algorithm has $n$ elements and $A$ is an upper bound of the sum.
We have
$$
T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)
$$
Which shows $T_A(n) = \tilde{O}(n A)$.
The hidden $\log$ factor is $\log n \log nA$.
If anybody care about the $\log$ factors, with careful analysis we can prove the time complexity for Chao's algorithm is $O(nA\log(nA))$.
Proof. At the even-th layer of the recursion tree, we partition the set $S$ into two equally sized set $S_1$ and $S_2$, which gives $$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$$ and at the odd-th layer of the recursion tree, we partition the set $S$ into two "equally sumed" set $S_1$ and $S_2$. To be precise, we can partition a set $S$ with sum $A$ into two sets $S_1$ and $S_2$ with each of them sum up to $\leq A/2$, with at most one element left. We can deal with that element with trivial dynamic programming in $O(A)$. This gives $$T_o(n,A)=T_e(n_1,A/2)+T_e(n-n_1,A/2)+O(nA\log(nA)),$$ where $n_1=|S_1|$. Therefore we have $$T(n,A)\leq \sum_{i=1}^4T(n_i,A_i)+O(nA\log(nA)),$$ where $\sum_{i=1}^4n_i\leq n$, $\sum_{i=1}^4A_i\leq A$, and $\forall i,~n_i\leq n/2,~A_i\leq A/2$. This will give us $T(n,A)=O(nA\log(nA))$.
