3-partition Problem

The 3-partition problem is an NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m positive integers, can S be partitioned into m subsets S₁, S₂, …, S_m such that the sum of the numbers in each subset is equal? The subsets S₁, S₂, …, S_m must form a partition of S in the sense that they are disjoint and they cover S. Let B denote the (desired) sum of each subset S_i, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains NP-complete when every integer in S is strictly between B/4 and B/2. In this case, each subset S_i is forced to consist of exactly three elements (a triple).

The 3-partition problem is similar to the partition problem, which in turn is related to the subset sum problem. In the partition problem, the goal is to partition S into two subsets with equal sum. In 3-partition the goal is to partition S into m subsets (or n/3 subsets), not just three subsets, with equal sum.