ANSWER 4 and 5

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. 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.) 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