https://DevOpsCloud.io -- Cloud Monk Losang Jinpa

In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S₁ and S₂ such that the sum of the numbers in S₁ equals the sum of the numbers in S₂. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".

There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S₁, S₂ such that the difference between the sum of elements in S₁ and the sum of elements in S₂ is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.

The partition problem is a special case of two related problems:

• In the subset sum problem, the goal is to find a subset of S whose sum is a certain target number T given as input (the partition problem is the special case in which T is half the sum of S).
• In multiway number partitioning, there is an integer parameter k, and the goal is to decide whether S can be partitioned into k subsets of equal sum (the partition problem is the special case in which k = 2).

However, it is quite different to the 3-partition problem: in that problem, the number of subsets is not fixed in advance – it should be |S|/3, where each subset must have exactly 3 elements. 3-partition is much harder than partition – it has no pseudo-polynomial time algorithm unless P = NP.