## 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

0

0

0

1

1

0

0

0