A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Karl Bringmann · 2017
Given a set Z of n positive integers and a target value t, the SuBSETSuM problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves SuBSETSuM in time O(nt). This has been improved to O(nmaxZ) by Pisinger [J. Algorithms’99] and recently to by Koiliaris and Xu [SODA’17]. Here we present a simple and elegant randomized algorithm running in time Õ (n+1). This improves upon a classic algorithm and is likely to be near-optimal, since it matches conditional lower bounds from SetCoyer and k-Clique. We then use our new algorithm and additional tricks to improve the best known polynomial space solution from time Õ(n3t) and space Õ(n2) to time Õ(nt) and space Õ(nlogt), assuming the Extended Riemann Hypothesis. Unconditionally, we obtain time Õ(nt1+e) and space Õ(nte) for any constant ∊ > 0.