Let A=[a1,,an] be an array of n natural numbers. Given a number tN, we say t is a subset sum of A if there is a subset of indices S{1,,n} such that iSai=t. For example, if A=[1,3,5,7] then 12 is a subset sum of A since 5+7=12, but 2 is not. We want to design an algorithm that determines whether a given number tN is a subset sum of A. Specifically, when given A=[a1,,an] and tN as input, the algorithm should output 1 if t is a subset sum of A, and 0 otherwise. The algorithm should output an answer (either 0 or 1 ) for any given tN. We will use dynamic programming to solve this problem. The subproblem in your DP algorithm should be SubsetSum, which is defined as SubSETSum [i][t]={10iftisasubsetsumofthefirstielementsA1:i=[a1,,ai],otherwise. Also, let us define M=i=1nai, which is the sum of all numbers in A. The quantity M may appear in the size of the DP array and the run-time of your algorithm. 2. In general, what is the size of the DP array containing values for SuBSETSUM? (Hint: What is the largest number you could even conceivably obtain as a subset sum of A ? You may want to make use of M for your expression.) 3. State the base cases and their values. 4. Give and justify the recurrence SubSETSum should satisfy. (Hint: Given inputs i and t, we can either use the i-th element ai or not use it in the subset sum for t. If we use ai, then the remaining subset sum is tai which is less than t.)