Pseudopolynomial time number partitioning

In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem.

The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible.

Suppose the input to the algorithm is a multiset

: Let K be the sum of all elements in S. That is: K = x1 + ... + xN.

We will build an algorithm that determines whether there is a subset of S that sums to

The goal of our algorithm will be to compute p(

In aid of this, we have the following recurrence relation: The reasoning for this is as follows: there is some subset of S that sums to i using numbers if and only if either of the following is true: The algorithm consists of building up a table of size

Once the entire table is filled in, we return

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.

Below is the table P for the example set used above S = {3, 1, 1, 2, 2, 1}: This algorithm runs in time O(K N), where N is the number of elements in the input set and K is the sum of elements in the input set.

The algorithm can be extended to the k-way multi-partitioning problem, but then takes O(n(k − 1)mk − 1) memory where m is the largest number in the input, making it impractical even for k = 3 unless the inputs are very small numbers.

[1] This algorithm can be generalized to a solution for the subset sum problem.