A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum

Ce Jin, Hongxun Wu

Given a multiset $S$ of $n$ positive integers and a target integer $t$, the Subset Sum problem asks to determine whether there exists a subset of $S$ that sums up to $t$. The curre…