Beating Bellman's Algorithm for Subset Sum

Karl Bringmann, Nick Fischer, Vasileios Nakos

Bellman's algorithm for Subset Sum is one of the earliest and simplest examples of dynamic programming, dating back to 1957. For a given set of $n$ integers $X$ and a target $t$, i…