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

摘要

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 current best deterministic algorithm, by Koiliaris and Xu [SODA'17], runs in O~(sqrt{n}t) time, where O~ hides poly-logarithm factors. Bringmann [SODA'17] later gave a randomized O~(n + t) time algorithm using two-stage color-coding. The O~(n+t) running time is believed to be near-optimal.In this paper, we present a simple and elegant randomized algorithm for Subset Sum in O~(n + t) time. Our new algorithm actually solves its counting version modulo prime pt, by manipulating generating functions using FFT.