Beating Bellman’s Algorithm for Subset Sum
Karl Bringmann, Nick Fischer, Vasileios Nakos · Society for Industrial and Applied Mathematics eBooks · 2025
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, it computes the set of subset sums S (X, t ) (i.e., the set of integers s ∈ [0… t] for which there is a subset of X summing to s ) in time O (|S (X, t )| · n ). Since then, it has been an important question whether Bellman’s seminal algorithm can be improved.