5
$\begingroup$

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!

Improve this question
$\endgroup$
14
  • $\begingroup$ @awoodland Why's that? CST faq suggests otherwise. $\endgroup$
    – Nikita Rybak
    Commented Jan 30, 2011 at 13:09
  • 2
    $\begingroup$ Does O(2^(n/2)) count as better? $\endgroup$
    – IVlad
    Commented Jan 30, 2011 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
    Commented Jan 30, 2011 at 13:20
  • 1
    $\begingroup$ @IVlad no 2^n/2 is not better... $\endgroup$
    – Firebrandt
    Commented Jan 30, 2011 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
    Commented Feb 2, 2011 at 11:33

0

Reset to default

Browse other questions tagged or ask your own question.