Faster Pseudopolynomial Time Algorithms for Subset Sum

摘要

Given a (multi) set S of n positive integers and a target integer u, the subset sum problem is to decide if there is a subset of S that sums up to u. We present a series of new algorithms that compute and return all the realizable subset sums up to the integer u in (O) over tilde (min{root nu,u(5/4), sigma}), where sigma is the sum of all elements of S and (O) over tilde hides polylogarithmic factors. We also present a modified algorithm for integers modulo m, which computes all the realizable subset sums modulo m in (O) over tilde (min{root nm, m(5/4)}) time.