= Subset sum dynamic programming
{title2=$D_i(t)$}
For indexed occurrences with <positive integer> weights, let $D_i(t)$ record whether a <subset> of the first $i$ entries has sum $t$. The recurrence chooses whether the last occurrence is absent or present: $D_i(t)=D_{i-1}(t)\lor D_{i-1}(t-a_i)$, with an out-of-range term false. Initialize only sum zero true. Descending one-dimensional updates prevent reusing the current occurrence. Time is $O(ns)$ for target $s$ and space $O(s)$; positivity permits immediate rejection above the total. With weights bounded by $k$, the total is at most $nk$, making the bound <polynomial> in $n,k$.
Back to article page
