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 ${\displaystyle S}$ of cardinality ${\displaystyle N}$:

S = {x₁, ..., x_N}

Let K be the sum of all elements in S. That is: K = x₁ + ... + x_N. We will build an algorithm that determines whether there is a subset of S that sums to ${\displaystyle \lfloor K/2\rfloor }$. If there is a subset, then:

if K is even, the rest of S also sums to ${\displaystyle \lfloor K/2\rfloor }$

if K is odd, then the rest of S sums to ${\displaystyle \lceil K/2\rceil }$. This is as good a solution as possible.

e.g.1 S = {1, 2, 3, 5}, K = sum(S) = 11, K/2 = 5, Find a subset from S that is closest to K/2 -> {2, 3} = 5, 11 - 5 * 2 = 1

e.g.2 S = {1, 3, 7}, K = sum(S) = 11, K/2 = 5, Find a subset from S that is closest to K/2 -> {1, 3} = 4, 11 - 4 * 2 = 3

Recurrence relation

We wish to determine if there is a subset of S that sums to ${\displaystyle \lfloor K/2\rfloor }$. Let:

p(i, j) be True if a subset of { x₁, ..., x_j } sums to i and False otherwise.

Then p(${\displaystyle \lfloor K/2\rfloor }$, N) is True if and only if there is a subset of S that sums to ${\displaystyle \lfloor K/2\rfloor }$. The goal of our algorithm will be to compute p(${\displaystyle \lfloor K/2\rfloor }$, N). In aid of this, we have the following recurrence relation:

p(i, j) is True if either p(i, j − 1) is True or if p(i − x_j, j − 1) is True

p(i, j) is False otherwise

The reasoning for this is as follows: there is some subset of S that sums to i using numbers

x₁, ..., x_j

if and only if either of the following is true:

There is a subset of { x₁, ..., x_j−1 } that sums to i;

there is a subset of { x₁, ..., x_j−1 } that sums to i − x_j, since x_j + that subset's sum = i.

The pseudo-polynomial algorithm

The algorithm consists of building up a table of size ${\displaystyle \lfloor K/2\rfloor }$ by ${\displaystyle N}$ containing the values of the recurrence. Remember that ${\displaystyle K}$ is the sum of all ${\displaystyle N}$ elements in ${\displaystyle S}$. Once the entire table is filled in, we return ${\displaystyle P(\lfloor K/2\rfloor ,N)}$. Below is a depiction of the table ${\displaystyle P}$. 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.

Dependencies of table entry (i, j)

function can_be_partitioned_equally(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 (${\displaystyle \lfloor K/2\rfloor }$ + 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 ${\displaystyle \lfloor K/2\rfloor }$
        for j from 1 to n
            x = S[j-1]
            if (i-x) >= 0 then
                P(i, j) ← P(i, j-1) or P(i-x, j-1)
            else
                P(i, j) ← P(i, j-1)

   return P(${\displaystyle \lfloor K/2\rfloor }$, n)

Example

Below is the table P for the example set used above S = {3, 1, 1, 2, 2, 1}:

Result of example execution of algorithm on the table P

Analysis

This algorithm runs in time O(K/2 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)m^{k − 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.

References

1. Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI.