# Number of ways to partition a set into three subsets with given sum.

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 ?

• 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 7:13

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$.
• @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 2 '16 at 2:31