An Improved Pseudopolynomial Time Algorithm for Subset Sum

We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposes an Õ(n + t)-time algorithm [Bringmann SODA'17], and an open question has naturally arisen: can Subset Sum be solved in $O(n + w)$ time? Here w is the maximum integer in X. We make a progress towards resolving the open question by proposing an Õ(n + √wt)-time algorithm.