An Improved Pseudopolynomial Time Algorithm for Subset Sum
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang · 2024
We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set$X$of$n$positive integers and a target$t$, Subset Sum asks whether some subset of$X$sums to$t$. Bringmann proposes an$\tilde{O}(n+t)$-time algorithm [Bringmann SODA'17], and an open question has naturally arisen: can Subset Sum be solved in$O(n+w)$time? Here$w$is the maximum integer in$X$. We make a progress towards resolving the open question by proposing an$\tilde{O}(n+\sqrt{wt})$-time algorithm.