In computer science, the Partition Problem is an NP-complete problem, seen as a decision problem, consisting of deciding whether, given a multi-set of integers, it can be partitioned into two "halves" such that adding the elements of each, both give the same result.
More precisely, given a multi-point S of integers: is there any way to partition S into two subsets S1 and S2, such that the sum of the elements in S1 is equal to the sum of the elements in S2? > The partition problem is equivalent to a particular case of the subset sum problem, which says: Given a set S of integers, is there any subset S1 of S whose elements add up to exactly t / 2, where t is the sum of all the elements of S? The equivalence can be seen by defining S2 as the difference S - S1. Therefore, the solution with existing dynamic programming to solve the problem of addition of subsets, using pseudo-polynomial time, is also applicable to the problem of partition.
A variation of this problem is the 3-partition problem, where the set S must be partitioned into | S | / 3 subsets that add up the same. Unlike the partition problem, this problem is not solved in pseudo-polynomial time, unless P = NP: this is because the 3-partition problem remains in the NP-complete class even using unary encoding.
wiki