# 2 partition problem with equal cardinality [duplicate]

Possible Duplicate:
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 * Sum of set)

Can I do better than this?

• Does O(2^(n/2)) count as better? Jan 30 '11 at 13:17