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 SubSETSumU[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. 1. Suppose A=[2,1,3]. Fill out the following table for A. Note that we define the sum over the empty set to be 0 . The pre-filled entries in the top left corner correspond to SuBSETSUM [0][0]=1 and SubsetSum [0][1]=0 Table 1: Fill in the entries for SubsetSum [i][t]. 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.) 5. Based on the recurrence, write pseudocode that computes SuBSETSum and outputs whether a given t can be written as a subset sum of A. State and explain the run time of your algorithm as a big- expression. You may want to use M for your expression