[Solved]: Partition problem with distinct integers

Problem Detail: 

Partition problem is a well known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers and we want to decide the existance of a partition into two sets that have the same sum.

Is the partition problem still NP-complete if all input integers are distinct (no integer is repeated)?

Asked By : Mohammad Al-Turkistany

Answered By : Yuval Filmus

Here is an outline of a reduction from PARTITION to UNIQUE PARTITION. Suppose the original numbers are $x_1,\ldots,x_n$ and the target is $T$. I assume that all $x_i$ are positive integers. The new numbers are going to be $2^n x_i + i$, as well as $1,2,4,\ldots,2^{n/2}$, and the new target is $2^n T + 2^{n/2}$. (The numbers $2^n,2^{n/2}$ are quite arbitrary and could be made much smaller.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13030

3.2K people like this

 Download Related Notes/Documents