Faster Pseudopolynomial Time Algorithms for Subset Sum

摘要: Given a (multi) set S of n positive integers and target integer u, the subset sum problem is to decide if there that sums up u. We present series new algorithms compute return all realizable u in O(min l Snu,u5/4,σ r), where σ elements O hides polylogarithmic factors. also modified algorithm for modulo m, which computes m Snm,m5/4r) time.Our contributions improve upon standard dynamic programming runs O(nu) time. To best our knowledge, are fastest deterministic this problem. The results can be employed various algorithmic problems, from graph bipartition computational social choice. Finally, we result on covering Zm, might independent interest.