0
$\begingroup$

Given a finite sequence of natural numbers. Determine wether it is possible to divide the numbers into two sets such as totals of both sets are equal. Show one variant of such distribution. Is there any subset of initial set with total of 100.

Now I only see a bruteforce approach to this problem - check totals of all of S(n,2) (Stirling number of the second kind) combinations for equality and show one such combination. And also check all possible combinations of initial set for equality to 100. Is there more elegant solution?

$\endgroup$
1
$\begingroup$

This is the partition problem, a well-known NP-complete problem.

This means that no "elegant" solution is known assuming that we require as a necessary condition for "elegance" that it can be proven to require only a polynomial amount of work.

However, if the numbers themselves (or the target sum) are small, there is a good dynamic programming algorithm; see the above linked Wikipedia article.

$\endgroup$
1
$\begingroup$

This is called the "Set partition problem", and is NP-complete. However, there are good heuristic methods (e.g. Karmarkar-Karp), and a pseudo-polynomial dynamic programming algorithm. In particular it's very easy to check if there is a subset of sum $100$ using dynamic programming.

$\endgroup$
-1
$\begingroup$

This is an NP problem, which means that it can only be solved in non-polynomial time, in this case if the set is called $S$, then the NP approach will cost: $$(|S|-1)!$$ steps (at least that's the fastest I method know of). If you find a way to do it in polynomial time, you'll have proven that P=NP and you'll win a millennium prize (also if you prove that such an approach does not exist).

$\endgroup$
  • 1
    $\begingroup$ No, that's not what NP means. $\endgroup$ – Robert Israel Sep 22 '15 at 19:49
  • $\begingroup$ The problem is NP-complete. Merely being in NP (without being complete) doesn't mean that the problem is hard -- checking whether a number is odd or even is in NP too. And even "NP-complete" doesn't guarantee that the problem has no polynomial solutions, only that it would surprise almost everybody if it had because that would imply that all problems in NP have polynomial-time solutions. $\endgroup$ – hmakholm left over Monica Sep 22 '15 at 19:50
  • $\begingroup$ ah, NP-complete. I knew there was a special term. thanks for the extra info! $\endgroup$ – Mastrem Sep 22 '15 at 20:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.