There is a similar question that has been asked, but my question addresses particular detail of an answer.

I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description:

SUBSET-SUM is defined as follows: Given a set X of integers and a target number t, find a subset Y from X such that the members of Y add up to exactly t. Let s be the sum of members of X. Feed X' = X U {s - 2t} into SET-PARTITION. Accept if and only if SET-PARTITION accepts.

What does "X' = X U {s - 2t}" (union?) and "Feed X' = X U {s - 2t} into SET-PARTITION" mean? How does this prove that SUBSET-SUM can be reduced to SET-PARTITION?

  • $\begingroup$ Yup, that means union. $\endgroup$
    – D.W.
    Jul 18, 2015 at 5:17

1 Answer 1


What you are doing here is adding a new element to your original set 'X'. The value for this new element is (s - 2t). Hence, X' now contains one extra element as compared to X.

The SET-PARTITION would "accept" if the provided set can be partitioned into two subsets with equal sum. We were already able to pick out a subset 'Y', from the set X, the sum of whose elements was 't'. If we include the extra element (s-2t) in this subset Y, the sum of its elements would now become ( t + s - 2*t ) = (s-t). This is also the sum of the elements which are remaining in the set (X - Y). Hence, X' can be divided into two subsets each of whose sum is (s-t).

  • $\begingroup$ I am confused. By 'S' you mean 'Y' right? $\endgroup$ Jul 18, 2015 at 17:45
  • $\begingroup$ Yes, I meant Y, I have updated my comment. $\endgroup$ Jul 19, 2015 at 6:05
  • $\begingroup$ Thanks! Took me a while to understand your answer. Whoever discovered this reduction must be a genius! $\endgroup$ Jul 20, 2015 at 1:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.