In number theory and computer science, the partition problem, or number partitioning,[1] is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. 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".[2][3]

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

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

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.[5]


Given S = {3,1,1,2,2,1}, a valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}. Both sets sum to 5, and they partition S. Note that this solution is not unique. S1 = {3,1,1} and S2 = {2,2,1} is another solution.

Not every multiset of positive integers has a partition into two subsets with equal sum. An example of such a set is S = {2,5}.

Computational hardness

The partition problem is NP hard. This can be proved by reduction from the subset sum problem.[6] An instance of SubsetSum consists of a set S of positive integers and a target sum T; the goal is to decide if there is a subset of S with sum exactly T.

Given such an instance, construct an instance of Partition in which the input set contains the original set plus two elements: z1 and z2, with z1 = sum(S) and z2 = 2T. The sum of this input set is sum(S) + z1 + z2 = 2 sum(S) + 2T, so the target sum for Partition is sum(S) + T.

Approximation algorithms

As mentioned above, the partition problem is a special case of multiway-partitioning and of subset-sum. Therefore, it can be solved by algorithms developed for each of these problems. Algorithms developed for multiway number partitioning include:

Exact algorithms

There are exact algorithms, that always find the optimal partition. Since the problem is NP-hard, such algorithms might take exponential time in general, but may be practically usable in certain cases. Algorithms developed for multiway number partitioning include:

Algorithms developed for subset sum include:

Hard instances and phase-transition

Sets with only one, or no partitions tend to be hardest (or most expensive) to solve compared to their input sizes. When the values are small compared to the size of the set, perfect partitions are more likely. The problem is known to undergo a "phase transition"; being likely for some sets and unlikely for others. If m is the number of bits needed to express any number in the set and n is the size of the set then tends to have many solutions and tends to have few or no solutions. As n and m get larger, the probability of a perfect partition goes to 1 or 0 respectively. This was originally argued based on empirical evidence by Gent and Walsh,[10] then using methods from statistical physics by Mertens,[11][12] and later proved by Borgs, Chayes, and Pittel.[13]

Probabilistic version

A related problem, somewhat similar to the Birthday paradox, is that of determining the size of the input set so that we have a probability of one half that there is a solution, under the assumption that each element in the set is randomly selected with uniform distribution between 1 and some given value. The solution to this problem can be counter-intuitive, like the birthday paradox.

Variants and generalizations

Equal-cardinality partition is a variant in which both parts should have an equal number of items, in addition to having an equal sum. This variant is NP-hard too.[5]: SP12  Proof. Given a standard Partition instance with some n numbers, construct an Equal-Cardinality-Partition instance by adding n zeros. Clearly, the new instance has an equal-cardinality equal-sum partition iff the original instance has an equal-sum partition. See also Balanced number partitioning.

Distinct partition is a variant in which all input integers are distinct. This variant is NP-hard too.[citation needed]

Product partition is the problem of partitioning a set of integers into two sets with the same product (rather than the same sum). This problem is strongly NP-hard.[14]

Kovalyov and Pesch[15] discuss a generic approach to proving NP-hardness of partition-type problems.


One application of the partition problem is for manipulation of elections. Suppose there are three candidates (A, B and C). A single candidate should be elected using a voting rule based on scoring, e.g. the veto rule (each voter vetoes a single candidate and the candidate with the fewest vetoes wins). If a coalition wants to ensure that C is elected, they should partition their votes among A and B so as to maximize the smallest number of vetoes each of them gets. If the votes are weighted, then the problem can be reduced to the partition problem, and thus it can be solved efficiently using CKK. The same is true for any other voting rule that is based on scoring.[16]


  1. ^ a b Korf 1998.
  2. ^ Hayes, Brian (March–April 2002), "The Easiest Hard Problem" (PDF), American Scientist, vol. 90, no. 2, Sigma Xi, The Scientific Research Society, pp. 113–117, JSTOR 27857621
  3. ^ Mertens 2006, p. 125.
  4. ^ Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI.
  5. ^ a b Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.
  6. ^ Goodrich, Michael. "More NP complete and NP hard problems" (PDF).
  7. ^ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Knapsack problems. Springer. p. 97. ISBN 9783540402862.
  8. ^ Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 978-0-471-92420-3. MR 1086874.
  9. ^ Korf, Richard E. (1995-08-20). "From approximate to optimal solutions: a case study of number partitioning". Proceedings of the 14th International Joint Conference on Artificial Intelligence. IJCAI'95. Vol. 1. Montreal, Quebec, Canada: Morgan Kaufmann Publishers. pp. 266–272. ISBN 978-1-55860-363-9.
  10. ^ Gent & Walsh 1996.
  11. ^ Mertens 1998.
  12. ^ Mertens 2001, p. 130.
  13. ^ Borgs, Chayes & Pittel 2001.
  14. ^ Ng, C. T.; Barketau, M. S.; Cheng, T. C. E.; Kovalyov, Mikhail Y. (2010-12-01). ""Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation". European Journal of Operational Research. 207 (2): 601–604. doi:10.1016/j.ejor.2010.05.034. ISSN 0377-2217.
  15. ^ Kovalyov, Mikhail Y.; Pesch, Erwin (2010-10-28). "A generic approach to proving NP-hardness of partition type problems". Discrete Applied Mathematics. 158 (17): 1908–1912. doi:10.1016/j.dam.2010.08.001. ISSN 0166-218X.
  16. ^ Walsh, Toby (2009-07-11). "Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule" (PDF). Written at Pasadena, California, USA. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. San Francisco, California, USA: Morgan Kaufmann Publishers Inc. pp. 324–329. Archived (PDF) from the original on 2020-07-10. Retrieved 2021-10-05.