Derandomizing Pseudopolynomial Algorithms for Subset Sum

Timothy M. Chan

We reexamine the classical subset sum problem: given a set $X$ of $n$ positive integers and a number $t$, decide whether there exists a subset of $X$ that sums to $t$; or more gene…