page_title: Partition problem
section_title: The pseudo-polynomial algorithm
hierarchical_section_title: Partition problem / Pseudo-polynomial time algorithm / The pseudo-polynomial algorithm
caption_attribution_description: English: A generic dynamic programming table for the Partition Problem in which a purple arrow from block A to block B means that the resultant value of block B depends (or might depend) on the value of block A. This is a result of the recurrence relation of the Partition Problem.
context_page_description: 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 can be viewed as a special case of the subset sum problem.
context_section_description: The algorithm consists of building up a table of size  by  containing the values of the recurrence. Remember that  is the sum of all  elements in . Once the entire table is filled in, we return . Below is a depiction of the table . There is a blue arrow from one block to another if the value of the target-block might depend on the value of the source-block. This dependence is a property of the recurrence relation.
  function find_partition(S) is
      input: A list of integers S.
      output: True if S can be partitioned into two subsets that have equal sum.
  
      n ← |S|
      K ← sum(S)
      P ← empty boolean table of size ( + 1) by (n + 1)
  
      initialize top row (P(0,x)) of P to True
      initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
  
      for i from 1 to 
          for j from 1 to n
              if (i-S[j]) >= 0 then
                  P(i, j) ← P(i, j-1) or P(i-S[j], j-1)
              else
                  P(i, j) ← P(i, j-1)
  
     return P(, n)
caption: Dependencies of table entry (i, j)
exif: {}