3. 5+10+10-25 points] (Subset Sum) The special case of the Exact Knapsack problem with wi - vi is known as the Subset Sum problem. In other words, we are given a sequence of positive integers wi, . . . , Wn a ecide whether there is a subset of the wi adding up to exactly W. (Here, we use this usual definition of "Subset Sum," even though our textbook uses term "Subset Sum" for the corresponding special case of the standard Knapsack problem.) nd a number W. We want to d (a) Write the recurrence equation (including the base case) for M[i, w defined as a boole an arrav. (b) Assume, you want to solve the counting problem associated with the Subset Sum problem, i.e., you want to compute the number of subsets S of (1,... ,n) such that ES Write pseudo-code for solving this counting problem. (c) Prove that your algorithm is correct by (strong) induction