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?
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|$.