Subset Sum–Dynamic Programming

Dynamic programming algorithm for subset sum

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 the 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 \text{ 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}$$ ...