2. Subset Sum

Acknowledgements

Some of this material is borrowed from Jeff Erickson’s chapters on Recursion, Backtracking, and Dynamic Programming. Check them out for a more detailed comparison between recursive and memoized implementations.

The Problem

• The Subset Sum takes as input an array $X$ of $n$ positive integers and a target $Y > 0$.
• The output is YES if there is a subset of the array $X[1 .. n]$ that sums to $Y$, and NO otheriwse.

The Solution

What are the fragments (AKA, what do we want to store)?

Let us try to project this problem on a prefix of the input array and a generic target.

For $1 \leq i \leq n$ and $1 \leq j \leq Y$, let:

$T[i,j] = $ TRUE if some subset of $X[1,\ldots,i]$ sums to $j$, and FALSE otherwise.

The $T$-values are our fragments.

Are the fragments going to be useful (AKA, where is the final answer)?

Indeed, when the projection covers the original input, we are done! So the answer we are looking for is the value of $T[n,Y]$.

Do we have a kickstart (AKA, what are the base cases)?

Note that:

$T[1,j]$ is TRUE if and only if $X[1] = j$.

How do the fragments come together (AKA, how do we compute the values that we have agreed to store)?

If $A[i] > j$: then $T[i,j]$ is TRUE if and only if ($T[i-1,j]$) is TRUE. Indeed, $A[i]$ cannot participate in any solution here, since the array $X$ only has positive integers, so we piggy back on whether a sum of $j$ can be obtained from the subarray up to $X[1,\ldots,i-1]$.

If $A[i] = j$: the return TRUE already, we have a solution comprising just of $A[i]$ and it is our lucky day!

Otherwise: $T[i,j]$ is TRUE if and only if ($T[i-1,j-A[i]] \lor T[i-1,j]$) is TRUE. Here, we take the best of both worlds by speculating on whether $A[i]$ contributes to the solution or not. If it does, we update the target to $j - A[i]$ — and notice that this is a legitimate index to ping since $j > A[i]$. If it does not, then as in the first situation, we fall back entirely on $A[1,\ldots,i]$ to carry the burden of producing a solution. If netiher of these scenarios pan out, then observe that there is no solution at all.

Can we put the pieces together without getting stuck (AKA, are the dependencies in step #4 acyclic)?

It is straightforward to check that these dependencies are indeed acyclic.