# A Faster Pseudopolynomial Time Algorithm for Subset Sum

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

## Key facts

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

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

- [Photonic Quantum Computers](https://mlsanity.com/paper/2409.08229/) (2024)

## Abstract (arXiv)

Given a multiset 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. We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer u in widetildeO!left(min√nu,u4/3,σright), where σ is the sum of all elements in S and widetildeO hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in O(nu) time. To the best of our knowledge, the new algorithm is the fastest general algorithm for this problem. We also present a modified algorithm for cyclic groups, which computes all the realizable subset sums within the group in widetildeO!left(min√nm,m5/4right) time, where m is the order of the group.