Subset Sum in Almost-Linear Time

Abstract

We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\dots ,a_n\le \Delta$ that sums to the target $t$ in $\mathcal{O}(n+{\Delta }^{1+o(1)})$ time. This improves upon the previous $\tilde{\mathcal{O}}(n+{\Delta }^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on $\Delta$ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.