Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation!

Is it possible to reduce this problem using a Levin Reduction ?

If you don't understand write for clarification!


5 Answers 5


Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$. Let $L'$ be the list formed by adding $S+B,2S-B$ to $L$. Observe that $\sum L' = 4S$

($\implies$) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ 2S-B \}$ and $L\setminus M \cup \{ S+B \}$. Indeed, the first part sums to $B+(2S-B) = 2S$, and the second to $(S-B)+(S+B) = 2S$.

($\impliedby$) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then we will prove there is a sublist of $L$ summing to $B$.

Recall that since $\sum L' = 4S$ then $\sum P_1 = \sum P_2 = 2S$.

Note that $(S+B)+(2S-B) = 3S \ne 2S$ therefore these two elements reside in opposite sides of the partition.

Without loss of generality, suppose that $2S-B \in P_1$. Therefore the rest of $P_1$'s must come exactly from $L$ and must sum to $B$ which, so that we've found a sublist which sums to $B$, as needed.

  • 2
    $\begingroup$ But the standard subset-sum problem uses all integers, and partition problem uses just non-negative integers... $\endgroup$
    – gukoff
    Commented Apr 19, 2013 at 17:40
  • $\begingroup$ SUBSET-SUM is NP-complete even with non-negative integers, for example the reduction from 3SAT ends up with non-negative integers. Also, there is probably a direct reduction from integer SUBSET-SUM to non-negative integer SUBSET-SUM. $\endgroup$ Commented Apr 19, 2013 at 20:26
  • 1
    $\begingroup$ Yes, I know, and this reduction is very easy. Just noting that it isn't the subset sum in it's "default" form. :) $\endgroup$
    – gukoff
    Commented Apr 20, 2013 at 3:11
  • $\begingroup$ Would it also work if $L^{'}$ is $L \bigcup \{B, S-B\}$? as $|\{B, S-B\}| = B$, like $|L| = B$ $\endgroup$ Commented Feb 28, 2014 at 17:42
  • 1
    $\begingroup$ @Issam It wouldn't, this the PARTITION instance would always have the solution $L,\{B,S-B\}$. $\endgroup$ Commented Feb 28, 2014 at 21:48

The answer mentioned by @Yuval Filmus is incorrect (it's correct ONLY if there are no negative integers). Consider the following multiset :

$$\{-5, 2, 2, 2, 2, 2\} $$

and the target sum is $-2$. We know that there is no subset. Now, we construct the instance for the partition problem. The two new elements added are $2\sigma-t = 12$ and $\sigma+t = 3$. The multiset is now: $$\{-5, 2, 2, 2, 2, 2, 3, 12\}$$ and the total sum is $20$.

The partition problem solves the answer giving the subset $$\{2, 2, 2, 2, 2\}$$ Here, the 2 new elements are in the same subset (there is no other way to partition into half the sum). Hence, this is a counter example. The correct answer is as follows:

Add an element whose value is $2t-\sigma$. The total sum of the multiset is now $2t$. Solve the partition problem which will give 2 subsets of sum $t$. Only one of the partition will contain the new element. We choose the other partition whose sum is $t$ and we have solved the subset problem by reducing it into a partition problem. This is what the link explains.

  • 2
    $\begingroup$ But, as Yuval says in a comment to his answer, subset sum is NP-complete even if we restrict to positive integers. So we can assume that there are no negative numbers. $\endgroup$ Commented Apr 15, 2017 at 14:13
  • 1
    $\begingroup$ Yes, I agree, subset sum is NP-complete even in case of positive integers. I was just providing a more complete proof for any integer. $\endgroup$ Commented Apr 15, 2017 at 15:31
  • 2
    $\begingroup$ "Just providing a more complete proof" and also wrongly claiming that an existing answer is incorrect. $\endgroup$ Commented Apr 15, 2017 at 16:33
  • 2
    $\begingroup$ It's incorrect in the sense that it does not work for negative integers. :) Peace :) $\endgroup$ Commented Apr 15, 2017 at 16:43

Here is a straightforward proof:

It is easy to see that SET-PARTITION can be verified in polynomial time; given a partition $P_1,P_2$ just sum the two and verify that their sums equal each other, which is obviously a polynomial time verification (because summation is a polynomial operation and we are only performing at most $|X|$ many summations).

The core of the proof is in reducing SUBSETSUM to PARTITION; to that end given set $X$ and a value $t$ (the subset sum query) we form a new set $X'=X \cup \{s-2t\}$ where $s=\sum_{x \in X}x$. To see that this is a reduction:

  • ($\implies$ ) assume there exists some $S \subset X$ such that $t=\sum_{x \in S}x$ then we would have that \begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*} \begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*} and we would have that $S\cup \{ s-2t \} $ and $X' \setminus( S\cup \{s-2t\})$ form a partition of $X'$

  • ($\impliedby $) Suppose that there is a partition $P_1',P_2' $ of $X'$ such that $\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$. Notice that this induces a natural partition $P_1$ and $P_2$ of $X$ such that WLOG we have that \begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*} \begin{equation*} \implies s-2t+\sum_{x \in P_1}x+\sum_{x \in P_1}x= \sum_{x \in P_2}x+\sum_{x \in P_1}x = s \end{equation*} \begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*} \begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}

Hence from a solution $t=\sum_{x \in S}x$ we can form a parition $P_1 =S\cup \{ s-2t \} $, $P_2=X' \setminus( S\cup \{s-2t\})$ and conversely from a partition $P_1',P_2' $ we can form a soltuion $t=\sum_{x \in P_1'\setminus \{s-2t\}}x$ and therefore the mapping $f:(X,t)\rightarrow X'$ is a reduction (because $(X,t)$ is in the language/set SUBSETSUM $\Leftrightarrow X'=f(X,t)$ is in the language/set PARTITION) and it is clear to see that the transformation was done in polynomial time.


Subset Sum:

Input: {a1,a2,...,am} s.t M={1..m} and ai are non negative integer and S⊆{1..k} and Σai(i∈S) = t


Input: {a1,a2,...,am} and S⊆ {1,· · ·,m} s.t Σai(i∈S) = Σaj(j∉S)

Partition Np Proof: if prover provides a partitions(P1,P2) for verifier, verifier can easily calculate the sum of P1 and P2 and check if the result is 0 in linear time.

NP_Hard: SubsetSum ≤p PARTITION

Let x be input of SubsetSum and x=〈a1,a2,...,am,t〉 and Σai(i from 1 to m) = a

Case1: 2t >= a:

Let f(x)=〈a1,a2,...,am,am+1〉 where am+1= 2t−a

We want to show that x∈SubsetSum ⇔ f(x)∈PARTITION

so there exist S⊆ {1,...,m} s.t T = {1..m} - S and Σai(i∈T) = a-t

and Let T' = {1...m,m+1} - S so Σaj(j∈T') = a-t+2t-a = t

which is exactly Σai(i∈S)= t and it shows f(x)∈PARTITION

now We also will show that f(x)∈PARTITION ⇔ x∈SubsetSum

so there exist S⊆ {1,...,m,m+1} s.t T = {1,...,m,m+1} - S and Σai (i∈T)= [a+(2t-a)-t]=t

and it shows Σai(i∈T) = Σaj(j∈S) so m+1∈T and S⊆ {1,· · ·,m} and Σai(i∈S)= t

so x∈SubsetSum

Case 2: 2t =< a :

we can check same but just this time am+1 is a−2t


this link has a good description of both reductions, partition to subset-sum and subset-sum to partition. I think it is more obvious than YUVAL's answer. useful link

  • 4
    $\begingroup$ Please do not post link-only answers. If the content at the link changes or becomes unavailable, your answer will become useless. Please amend your answer so that it is useful, even if the link is unavailable (for instance, restating the content in your own words and providing the link as reference and source). $\endgroup$ Commented Jan 16, 2016 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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