Subscribe to the weekly news from TrueShelf

0

Subset Sum vs Partition

Consider the following problems :

Partition problem : Given a collection of \(n\) integers \(a_1, a_2, \ldots, a_n\), is there a subset \(I~\subset~{1,2, \ldots, n }\) such that \(\sum_{i~\in~I}a_i~=~\sum_{i~\not\in~I}a_i\) ?

Subset Sum problem : Given a collection of \(n\) integers \(a_1, a_2, \ldots, a_n\) and an integer \(B\), is there a subset \(I~\subseteq~{1,2, \ldots, n }\) such that \(\sum_{i~\in~I}a_i~=B\) ?

  • Give a polynomial time reduction from the partition problem to the subset sum problem.

  • Give a polynomial time reduction from the subset sum problem to the partition problem.

Source: folklore