Subset Sum-Dynamic Programming

Dynamic programming algorithm for subset sum problem

Recall that the $SubsetSum$ 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{array}{ll}& Trueift=0\\ & Falseift<0ori>n\\ \end{array}$$ ...