Derandomizing Pseudopolynomial Algorithms for Subset Sum

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 generally, compute the set out of all numbers \(y \in \{0,\ldots,t\}\) for which there exists a subset of \(X\) that sums to \(y\). Standard dynamic programming solves the problem in \(O(tn)\) time. In SODA’17, two papers appeared giving the current best deterministic and randomized algorithms, ignoring polylogarithmic factors: Koiliaris and Xu’s deterministic algorithm runs in \(\widetilde{O}(t\sqrt{n})\) time, while Bringmann’s randomized algorithm runs in \(\widetilde{O}(t)\) time. We present the first deterministic algorithm running in \(\widetilde{O}(t)\) time.