The 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 two "halves" that have the same sum. More precisely, given a multiset S of integers, is there a way to partition S into two subsets S₁ and S₂ such that the sums of the numbers in each subset are equal? The subsets S₁ and S₂ must form a partition in the sense that they are disjoint and they cover S.

The partition problem is equivalent to the following special case of the subset sum problem: given a set S of integers, is there a subset S₁ of S that sums to exactly t/2 where t is the sum of all elements of S? (The equivalence can be seen by defining S₂ to be the difference S − S₁.) Therefore, the pseudo-polynomial time dynamic programming solution to subset sum applies to the partition problem as well.

A variation of the partition problem is the 3-partition problem, in which the set S must be partitioned into |S|/3 triples each with the same sum. In contrast to partition, 3-partition has no pseudo-polynomial time algorithm unless P = NP: 3-partition remains NP-complete even if the numbers are encoded in unary.

See also

• Subset sum problem
• Bin packing problem

NP-complete problems

Partitionsproblem