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 ∈ 0, . . . , 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 O(t √ n) time, while Bringmann's randomized algorithm runs in O(t) time. We present the first deterministic algorithm running in O(t) time.

Our technique has a number of other applications: for example, we can also derandomize the more recent output-sensitive algorithms by Bringmann and Nakos [STOC'20] and Bringmann, Fischer, and Nakos [SODA'25] running in O(|OUT| 4/3 ) and O(|OUT| √ n) time, and we can derandomize a previous fine-grained reduction from 0-1 knapsack to min-plus convolution by Cygan et al. [ICALP'17].