Subset Sum in Almost-Linear Time

Ce Jin, Xiao Mao

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 impro…