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?

Thanks in advance!


marked as duplicate by Tsuyoshi Ito, Kaveh, Suresh Venkat Feb 2 '11 at 17:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from stackoverflow.com Feb 2 '11 at 11:25

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ @awoodland Why's that? CST faq suggests otherwise. $\endgroup$ – Nikita Rybak Jan 30 '11 at 13:09
  • 2
    $\begingroup$ Does O(2^(n/2)) count as better? $\endgroup$ – IVlad Jan 30 '11 at 13:17
  • 2
    $\begingroup$ @awoodland, This isn't a CSTheory level problem and @Firebrandt I think this is exactly 2-Partition problem, see wiki for details, or clarify your question with more details. $\endgroup$ – Saeed Jan 30 '11 at 13:20
  • 1
    $\begingroup$ @IVlad no 2^n/2 is not better... $\endgroup$ – Firebrandt Jan 30 '11 at 14:35
  • 1
    $\begingroup$ The asker had (secretly) posted the same question both on cstheory.stackexchange.com and Stack Overflow, and the question on Stack Overflow was migrated here. Seems like another reason why simultaneous crossposting and crossposting without linking are bad. Voted to close as an exact duplicate. $\endgroup$ – Tsuyoshi Ito Feb 2 '11 at 11:33

Browse other questions tagged or ask your own question.