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}$$

Transforming recurrence into dynamic programming algorithm

We can transform this recurrence into a dynamic programming algorithm following the usual boilerplate.

• Subproblems: Each subproblem is described by an integer $i$ such that $1 ≤ i ≤ n + 1$, and an integer $t ≤ T$. However, subproblems with $t < 0$ are trivial, so there’s no point in memoizing them. Indeed, we can modify the recurrence so that those subproblems never arise:

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

• Data structure: We can memoize our recurrence into a two-dimensional array $S[1..n+1,0..T]$, where $S[i,t]$ stores the value of $SS(i,t)$.
• Evaluation order: Each entry $S[i, t]$ depends on at most two other entries, both of the form $SS[i + 1, ·]$. So we can fill the array by considering rows from bottom to top in the outer loop and considering the elements in each row in arbitrary order in the inner loop.
• Space and time: The memoization structure uses $O(nT)$ space. If $S[i+1, t]$ and $S[i + 1, t − X [i]]$ are already known, we can compute $S[i, t]$ in constant time, so the algorithm runs in $O(nT)$ time.

Here is the resulting dynamic programming algorithm: