A Faster Pseudopolynomial Time Algorithm for Subset Sum

Given a multiset $S$ of $n$ positive integers and a target integer $t$, the subset sum problem is to decide if there is a subset of $S$ that sums up to $t$. We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer $u$ in $\tilde{O}\text{\hspace{0.17em}⁣}(\min \{\sqrt{n}u,u^{4\mathrm{/}3},\sigma \})$, where $\sigma$ is the sum of all elements in $S$ and $\tilde{O}$ hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in $O(nu)$ time. To the best of our knowledge, the new algorithm is the fastest general algorithm for this problem. We also present a modified algorithm for cyclic groups, which computes all the realizable subset sums within the group in $\tilde{O}\text{\hspace{0.17em}⁣}(\min \{\sqrt{n}m,m^{5\mathrm{/}4}\})$ time, where $m$ is the order of the group.