Given an array A = [a1, a2, . . . , an] of nonnegative integers, consider the following problems: 1 P Partition: Determine wheth
er there is a subset P ⊆ [n] ([n] := {1, 2, · · · , n}) such that i∈P ai = P j∈[n]\P aj 2 Subset Sum: Given some integer k, determine whether there is a subset P ⊆ [n] such that P i∈P ai = k 3 Knapsack: Given some set of items each with weight wi and value vi , and fixed numbers W and V , determine whether there is some subset P ⊆ [n] such that P P i∈P wi ≤ W and i∈P vi ≥ V For each of the following clearly describe your reduction, justify runtime and correctness.(a) Find a linear time reduction from Subset Sum to Partition.(b) Find a linear time reduction from Subset Sum to Knapsack.
