5

I am sure you have already heard about this problem. Given a list of natural numbers, is it possible to divide them into two piles of equal sums? If yes, write two lines with objects in each pile.

Is this some well-known problem? Does it have a name? Is it NP-Complete? If not, what is the fastest solution?

1
  • 2
    If it is NP complete, it will still have a fastest solution. It'll just be slower.
    – SLaks
    Apr 13, 2011 at 17:32

1 Answer 1

6

This is the Partition problem, which is NP-Complete. It is a variant of Subset SUM.

Which is the fastest, really depends on the data you have. For instance, if they were bounded, you could use dynamic programming etc.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.