Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems

Nikhil Bansal, Shashwat Garg, Jesper Nederlof +1

We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with $n$ items using $O^{\ast }(2^{0.86n})$ time and polynomial space, where the $O^*(\cdot…