Pseudopolynomial time number partitioning

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, pseudopolynomial time number partitioning is a <a href="/facts/Pseudo-polynomial_time/7a35x5wN">pseudopolynomial time</a> algorithm for solving the <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a>.
The problem can be solved using <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> 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 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of cardinality 
 
 
 
 N
 
 
 {\displaystyle N}
 
:

S = {x1, ..., xN}
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 
 
 
 
 ⌊
 K
 
 /
 
 2
 ⌋
 
 
 {\displaystyle \lfloor K/2\rfloor }
 
. If there is a subset, then:

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

if K is odd, then the rest of S sums to 
 
 
 
 ⌈
 K
 
 /
 
 2
 ⌉
 
 
 {\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

Pseudopolynomial time number partitioning open-in-new

Pseudopolynomial time number partitioning