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 ?
Asked
Active
Viewed 1,274 times
3
-
The simpler problem, given a set of $n$ integers, to partition it into 2 sets with equal sum, is already NP-complete. – Gerry Myerson Jun 13 '14 at 07:13
1 Answers
2
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$.
Peter Woolfitt
- 21,114
-
1
-
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 ? – user155768 Jun 13 '14 at 07:33
-
1@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. – Ross Millikan Oct 02 '16 at 02:31