Question $4$:

Recall the problem Subset Sum which we solved in class using a dynamic programming algorithm. The problem was as follows:

INPUT: set $S=\{s_0,$dots,$s_{n-1}\}$ of non$-$negative integers, positive integer $B$ OUTPUT: subset $S^{\text{'}}$subeS such that ${\displaystyle \underset{xin{S}^{\text{'}}}{\overset{?}{}}}x=B,$ or $"$no solution" if no such $S^{\text{'}}$ exists. In English, the problem takes in a set of non$-$negative integers and a positive integer $B,$ and returns some subset of the set that sums to $B($or $"$no solution" if this is impossible$).$ We solved this problem with the following method:

The DP Steps for Subset Sum

$($a$)$ What values are we trying to compute in the table $T$ :

$T[i,j]=$ TRUE if there exists a subset $S^{\text{'}}$sube$\{s_0,$dots,$s_i\}$ such that ${\displaystyle \underset{xin{S}^{\text{'}}}{\overset{?}{}}}x=j$

$($b$)$ What is the DP$-$relation:

$T[i,j]$ is TRUE if:

T$[$i$-1,$j$]=$ TRUE $($don$\text{'}$t use $s_i)$ OR

$-j>s_i$ and $T[i-1,j-s_i]=$TRUE $($use $s_i$ and some other numbers$)$ OR

$s_i=j($use only $s_i)$

$($c$)$ How do we initialize the table:

$T[0,s_0]=$ TRUE

$T[0.x]=$ FALSE for all $x{s}_0.$

$($d$)$ What do we return at the end:

Return $T[n-1,B]$

Subset Sum Pseudocode

$T[0,s_0]=$ TRUE

$T[0,x]=$ FALSE for $x{s}_0$

For $i=1$ to $n-1$

For $j=0$ to $B$

$**T[i,j]=$ TRUE $if$:

$*T[i-1,j]=$ TRUE, $OR$

$*s_i==j,OR$

$*j>s_i$ and $T[i-1,j-s_i]=$ TRUE

$**$ Else set $T[i,j]=$ FALSE

Else set $T[i,j]=$ FALSE

Return $T[n-1,B]$

We will now examine a related problem: Subset Sum of a specific size. The formal problem statement is as follows:

INPUT: set $S=\{s_0,$dots,$s_{n-1}\}$ of non$-$negative integers, positive integer $B,$ target size $C,$ where $C$ is an integer in the range $1,n$

OUTPUT: subset $S^{\text{'}}$subS such that ${\displaystyle \underset{xin{S}^{\text{'}}}{\overset{?}{}}}x=B$ AND $|S^{\text{'}}|=C,$ or FALSE if no such $S^{\text{'}}$ exists.

Example: $S=\{2,5,7,30,42,50\},B=79$