Problems

Subset Sum#

Given a multiset of numbers $S$ and a desired total $t$, can we find a subset of $S$ that sums to $t$?

The partition problem is a special case of subset sum where $t = \frac{1}{2} sum(S)$.

Dynamic Programming#

A dynamic programming approach to subset sum builds a table of $|S|$ rows and $t$ columns.⁰¹ We use a fixed ordering over $S$. We iterate over $i \in |S|$, allowing ourselves to use the first $i$ elements in $S$ to construct sums. Our inner loop $j$ checks all possible sums in $0$ through $t$.

The key insight is that we can use the table to check whether previous sums were possible. To fill in a table entry at $(i,j)$ we’re asking whether the first $i$ elements of $S$ can make the sum $j$. We’ve already computed this for the first $i-1$ elements, so when we consider the $i$th element, there are two options:

1. We can total $j$ without using $S[i]$. Whether we can do this is recorded in the table entry at $(i-1, j)$.
2. We can total $j$ by including $S[i]$. To do this, we’d need to be able to make $j - S[i]$ using the first $i-1$ elements. Whether we can do this is recorded in the table entry at $(i-1, j - S[i])$

In summary, our entry at $(i,j)$ is the or of two previous cells:⁰²

$$(i, j) = (i-1, j) \lor (i-1, j - S[i])$$

At the end, we read off the table value for $(|S|, t)$.

This algorithm takes $O(|S|t)$ time and space.⁰³ It’s called a pseudo-polynomial time algorithm because $t$ grows exponentially in the number of bits required to specify it. (For more on this, see problem specification bits below.)

Reductions#

Interestingly, subset sum can also be reduced into a partition problem, too. Let $s = sum(S)$. Create a new multiset $S’$ that’s $S$ plus a new element $b = 2t - s$. This means $sum(S’) = s + b = s + 2t - s = 2t$. If we can solve the partition problem on $S’$, that means we’ll have split $S’$ into two subsets that each sum to $t$. Whichever set lacks $b$ is the solution to the original subset sum problem of $S$ and $t$.

Partition Problem#

Given a multiset of numbers $S$, can we split $S$ into two subsets of equal sum?

Observations:

• if $sum(S)$ is odd, this is impossible

The partition problem is a special case of subset sum. Trivial reduction: find a subset $S$ that sums to $t = \frac{1}{2}sum(S)$. (The other subset will also sum to $t$.)

Problem Specification Bits#

The number 1024 is 0b10000000000, which takes 11 bits to represent.⁰⁴ $2^{10} = 1024$ and $\log_2{1024} = 10$. In other words, it takes $O(\log n)$ bits to represent a number $n$.

So, if a problem’s runtime is based on the value of an input number ($n$), we need much fewer bits $O(\log n)$ to specify that number.

Put another way, assume we only have $b$ bits to specify an input number to a problem. The value we can construct using $b$ bits is $2^b$. So we can make the runtime take exponentially longer ($2^{b+1}$) by only increasing our problem specification linearly ($b+1$).

This analysis matters because of the way we measure algorithmic complexity. We care about the amount of “work” (bits) it takes to specify a problem’s input, and how much “work” (time, space) it correspondingly takes to solve it. Our analysis measures this ratio.