3
$\begingroup$

Given a set S, with n elements out of which if any element is repeating then it is repeated at maximum 2 times. How to count the number of ways in which S can be partitioned into 3 subsets such that the sum of elements in each subset is required to be A, B, C respectively which are given. Can there be a polynomial time algorithm for it ?

$\endgroup$
  • $\begingroup$ The simpler problem, given a set of $n$ integers, to partition it into 2 sets with equal sum, is already NP-complete. $\endgroup$ – Gerry Myerson Jun 13 '14 at 7:13
2
$\begingroup$

Nevermind the number of solutions - even the existence of a solution is a difficult problem!

We see this by noting that the problem is at least as hard as the subset-sum problem. Specifically, letting $A=0$ means that we need some subset of the original set to sum to $0$, which is exactly the subset-sum problem.

The subset-sum problem is NP-Complete, so if there existed a polynomial time algorithm to solve your question then $P=NP$.

$\endgroup$
  • 1
    $\begingroup$ See also en.wikipedia.org/wiki/Partition_problem $\endgroup$ – Gerry Myerson Jun 13 '14 at 7:14
  • $\begingroup$ Now i see it can't be solved in polynomial time. For smaller values of n, say <= 20, can we even have an exponential time solution to it ? $\endgroup$ – user155768 Jun 13 '14 at 7:33
  • 1
    $\begingroup$ @user155768: an exponential time solution is easy. There are only about $3^n/6$ ways to partition the subsets, then sum each and see if it works. $\endgroup$ – Ross Millikan Oct 2 '16 at 2:31

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.