# How can I reduce Subset Sum to Partition?

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!

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.

• But the standard subset-sum problem uses all integers, and partition problem uses just non-negative integers... Apr 19, 2013 at 17:40
• 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. Apr 19, 2013 at 20:26
• Yes, I know, and this reduction is very easy. Just noting that it isn't the subset sum in it's "default" form. :) Apr 20, 2013 at 3:11
• Would it also work if $L^{'}$ is $L \bigcup \{B, S-B\}$? as $|\{B, S-B\}| = B$, like $|L| = B$ Feb 28, 2014 at 17:42
• @Issam It wouldn't, this the PARTITION instance would always have the solution $L,\{B,S-B\}$. 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.

• 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. Apr 15, 2017 at 14:13
• 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. Apr 15, 2017 at 15:31
• "Just providing a more complete proof" and also wrongly claiming that an existing answer is incorrect. Apr 15, 2017 at 16:33
• It's incorrect in the sense that it does not work for negative integers. :) Peace :) 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

Partition:

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