The partition proble mis defined as follows:
Instance: a (multi-) set of integers s = {a₁,a₂,...,aₙ}.
Questions: Can S be partitioned into two (multi-)sets A and B such that the sum of the numbers in A is equal to the sum of the numbers in B?
It is known that Partition is NP-complete. Using this fact, the goal of this problem is to show that a relaxation of the Partition, defined below, is also NP-complete.