Suppose that we are given an array A of n nonnegative integers A[1], A[2], . . ., A[n]. We would like to decide if there exists subset of the elements of the array A such that the sum of the elements in this subset is exactly S. We would like to construct a dynamic programming algorithm to solve this problem.

As it is typical for dynamic programming algorithms, we introduce a function to characterize the solution. Let us assume that we introduce the function D[i,j] with the following meaning:

D[i,j] will be set to TRUE if and only if there exists a subset of the elements A[i],A[i+1],A[i+2],...,A[n] such that the sum of this subset is exactly j

Here we have, 1 i n + 1 and 0 j S.

Note that the way we define the function D[i,j] is different than the way it was formulated in and it is generally defined. In this question we define D[i, j] considering a subset of A[i], A[i + 1], A[i+2], . . . , A[n] as stated above. Any answer in which D[i, j] does not consider a subset of A[i], A[i+ 1], A[i + 2], . . . , A[n] will not be evaluated and will not get any partial grade.

(a) (5 points) By using this function, we can state the result we would like to find as D[ ... , ... ] (fillinthe blanks with appropriate values).

(b) (15 points) Finally, we also need to define the function by using a recurrence. Please write the recurrence for D[i, j]:

D[i, j] =