Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Jonathan Allcock, Yassine Hamoudi, Antoine Joux +2

Subset-Sum is an NP-complete problem where one must decide if a multiset of $n$ integers contains a subset whose elements sum to a target value $m$. The best-known classical and qu…