# Subset Sum Made Simple

arXiv: https://arxiv.org/abs/1807.08248 · HTML: https://mlsanity.com/paper/1807.08248/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [From Competition to Collaboration: Designing Sustainable Mechanisms Between LLMs and Online Forums](https://mlsanity.com/paper/2602.04572/) (2026)

## Abstract (arXiv)

Subset Sum is a classical optimization problem taught to undergraduates as an example of an NP-hard problem, which is amenable to dynamic programming, yielding polynomial running time if the input numbers are relatively small. Formally, given a set 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. Dynamic programming yields an algorithm with running time O(nt). Recently, the authors [SODA '17] improved the running time to tildeObigl(√ntbigr), and it was further improved to tildeObigl(n+tbigr) by a somewhat involved randomized algorithm by Bringmann [SODA '17], where tildeO hides polylogarithmic factors. Here, we present a new and significantly simpler algorithm with running time tildeObigl(√ntbigr). While not the fastest, we believe the new algorithm and analysis are simple enough to be presented in an algorithms class, as a striking example of a divide-and-conquer algorithm that uses FFT to a problem that seems (at first) unrelated. In particular, the algorithm and its analysis can be described in full detail in two pages (see pages 3-5).