The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple exact algorithm - checking all the possible partitions - takes time $O(n 2^n)$. Is there a more efficient exact algorithm?

NOTE: If the numbers are small integers, then it can be solved by a pseudo-polynomial algorithm, but I am interested in a problem with real numbers (e.g. "double"s in Java).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.