# Reduction of SUBSET-SUM to SET-PARTITION [duplicate]

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?

## marked as duplicate by Kyle Jones, D.W.♦, David Richerby, Juho, Luke MathiesonJul 21 '15 at 4:06

• Yup, that means union. – D.W. Jul 18 '15 at 5:17

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).

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