Subset Sum—Dynamic Programming

Dynamic programming algorithm for subset sum problem

Recall that the subset sum problem asks whether any subset of a given array $X [1 .. n]$ of positive integers sums to a given integer $T$. In a previous lesson, we developed a recursive subset sum algorithm that can be reformulated as follows. Fix the original input array $X [1 .. n]$ and define the boolean function $SS(i, t) = True$ if and only if some subset of $X [i .. n]$ sums to $t.$

We need to compute $SS(1, T)$. This function satisfies the following recurrence:

$SS(i,t)=\begin{cases} & True \hspace{4.72cm} if\space t=0 \\ & False \hspace{4.6cm} if\space t<0\space or\space i>n\\ & SS(i+1,t)\space \vee \space SS(i+1,t-X[i])\hspace{0.4cm} \text{otherwise} \end{cases}$ ...