Sum Finder

We are given the set of numbers $S = \{5, 8, 2, 4, 6\}.$ Our goal is to determine if $17$ can be obtained as a sum of a subset of $S$. While this can be determined by a brute-force attack, the goal is to use a dynamic programming approach.

We enumerate the elements of $S$ as $a_0, a_1, ..., a_4.$ Let $M$ be a 5-by-18 binary matrix such that $M[i,j]=1$ if some subset of $\{a_0,...,a_i\}$ sums up to $j,$ otherwise $M[i,j]=0.$

It is clear that $M[i,0]=1$ for all $i$ and $M[0,j]=0$ for $j\neq a_0$ and $M[0,a_0]=1.$

From the definition of $M,$ if follows that, for $i>0$:

$M[i,j]=M[i-1,j]$ if $0< j< a_i,$

$M[i,j]=1$ if $j=a_i,$ and

$M[i,j]=\max\{M[i-1,j],M[i-1,j-a_i]\}$ if $17> j>a_i.$

The last equality is determined by the following idea. If $M[i-1,j]=1,$ then $j$ can be formed as a sum of a subset of $\{a_0,...,a_i\}$ that does not include $a_i.$ If $M[i-1,j-a_i]=1,$ then $j$ can be formed as a sum of a subset of $\{a_0,...,a_i\}$ that does include $a_i.$ If $M[i-1,j]=M[i-1,j-a_i]=0,$ then there is no way to form $j$ as a sum of a subset of $\{a_0,...,a_i\}.$

Following the rules above, we give a complete characterization of $M$ as follows:

Since $M[4,17]=1$, we see that $17$ can be formed as a sum of a subset of $S$. Futhermore, the chart above can used to see that $17 = 4 + 8 + 5$.