Subset Sum in Almost-Linear Time

We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\dots ,a_n\le \mathrm{\Delta }$ that sums to the target $t$ in $\mathcal{O}(n+{\mathrm{\Delta }}^{1+o(1)})$ time. This improves upon the previous $\tilde{\mathcal{O}}(n+{\mathrm{\Delta }}^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on $\mathrm{\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.