Preprint
Subset Sum in Almost-Linear Time
Oct 2026 · 2 citations
Computer Science
Abstract
We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\ldots,a_n \le \Delta$ that sums to the target $t$ in $\mathcal{O}(n+\Delta^{1+o(1)})$ time. This improves upon the previous $\widetilde{\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.