# Polynomial complexity algorithm of partition problem with sets of equal size

Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ).

Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to that problem?

-

Yes. Given a list $S$ of positive integers, add $\max(S)\cdot \mathrm{length}(S)$ to each element, and denote the resulting list by $S'$. Run the algorithm for the partition problem on $S'$, and accept if and only if it accepts. This is correct because partitions $S'=S'_1\cup S'_2$ are equivalent to partitions $S=S_1\cup S_2$ where $|S_1|=|S_2|$.
My kudos for a nice method! I suppose that $\sum(S)$ instead of $\max(S)\cdot \mathrm{length}(S)$ is also satisfies the solution, right? –  alexander.myltsev Oct 19 '12 at 14:25
Yep. Another reduction would be to send $s\in S$ to $1+s\cdot \mathrm{length}(S)$. –  Colin McQuillan Oct 19 '12 at 14:43