Abstract
Given a set Z of n positive integers and a target value t, the SubsetSum problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves SubsetSum in time O(nt). Here we present a simple and elegant randomized algorithm running in time O~(n+t). This improves upon a classic result and is likely to be near-optimal, since it matches conditional lower bounds from SetCover and k-Clique.