$$Design a dynamic programming algorithm to solve the sum of subsets problem:$$

There are n positive integers, p$1,$ p$2,...,$ pn and a positive integer sum S$.$ Is there a subset A of the n integers A $\{$ p$1,...,$ pn$\}$ such that the sum of the integers in the subset is S$,($piApi$=$S$)?$ If there is such a subset the output of the program is true otherwise it is false.$$

Example: p$1=3,$ p$2=5,$ p$3=11$ and S $=16.$ In this case the output is true since p$2+$ p$3=16.$

Example: p$1=3,$ p$2=5,$ p$3=11$ and S $=18.$ In this case there is no solution, and the output is false.

$$

The problem can be solved with dynamic programming.

A Boolean matrix B with rows $0$ to n and columns $0$ to S is generated. For the examples above the matrix has rows $0$ to $3,$ and columns $0$ to $16.$

B$[$i$,$ s$]$ is true if a subset of the first i integers sums to s$,$ otherwise it is false.

The solution to the original problem is true if B$[$n$,$ S$]=$ true, otherwise it is false.

$(1)[5\%]$ Write the recurrence relation for the solution.