Verify and Solve a Subset Sum Instance

Use binary input length correctly and prove a dynamic-programming recurrence.

Problem

For positive integers $a_1,\ldots,a_m,T$, define $D(i,t)$ to mean that some subset of the first $i$ numbers sums to $t$. Derive a recurrence, solve the instance $\{3,5,6,11\},T=14$, and explain why the algorithm is pseudopolynomial rather than polynomial in the binary input length.

Hint 1

A solution either excludes $a_i$ or includes it and previously formed $t-a_i$.

Hint 2

The table has a column for every integer from $0$ through $T$, while binary encoding of $T$ uses only $\Theta(\log T)$ bits.

Full solution

Initialize $D(0,0)=\text{true}$ and $D(0,t)=\text{false}$ for $t>0$. For $i\ge1$,

The two disjuncts exactly partition subsets by whether they contain $a_i$, proving correctness by induction on $i$.

For the instance, $3+5+6=14$, so $D(4,14)$ is true; backtracking yields the selected subset $\{3,5,6\}$.

The table has $(m+1)(T+1)$ entries and can be filled in $O(mT)$ arithmetic/Boolean steps. This is polynomial in the numeric value $T$, but $T$ may be exponential in its binary length. Therefore this runtime does not establish that binary SUBSET-SUM is in P. Membership in NP follows separately from a selection-bit certificate and polynomial-time binary addition.

Checkpoint

“Pseudopolynomial” describes dependence on encoded numeric values; it is not the same as exponential on every instance.

Provenance note

Original exercise using the standard dynamic program. It does not rely on student submissions as sources.

Common mistakes

• Skipping a direction of correctness or an input-format edge case.
• Measuring resources against a numeric value rather than encoded input length.
• Treating an informal intuition as a proof of the stated bound.

Sources and verification

• 2026 transcript 15
• Garey-Johnson, SP13
• Corpus coverage note: No direct merged-summary coverage.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Open in the visualization gallery: Subset Sum dynamic programming