Faster pseudo-polynomial time algorithms for PARTITION 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 &lt; 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$.