# Variants of the 3-Partition problem

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known that the 3SAT problem has a plenty of variants. Are there some variants of the 3-Partition problem discussed in the literature?

• Did you try searching for any? You could immediately consider a variant where each integer occurs exactly or at most $k$ times, for some fixed $k$. – Juho Mar 8 '14 at 13:08
• @Juho I searched and found little. Thanks for your hint. I would prefer to the variants which have been considered in the literature. – hengxin Mar 8 '14 at 13:13

Input: A set $$X = \{a_1,a_2,\ldots,a_{3n}\}$$ of positive distinct integers, and a positive integer $$B$$ where $$\Sigma_{i=1}^{3n} a_i = nB$$, and $$B/4 < a_i < B/2$$, where $$i \in [3n]$$.
Question: Is there a partition of $$X$$ into $$n$$ triples such that the elements in each triple sum to $$B$$?
The problem is also NP-complete when $$B$$ is bounded above by a polynomial in $$n$$. For an "application", a reduction from the problem is used in  to show a certain graph problem is hard.