Given a set of n positive integers, the algorithm finds all the values t<=u such that there exists a subset that sums to t.
The running time is O(sqrt(n)u) with some extra polylog factors.
There is also a C++ implementation of the standard dynamic programming algorithm for subset sum. The DP table gets packed into 64 bit unsigned integers. It's probably the fastest possibe implementation of the O(nu) time algorithm without getting into ASM and parallelism.
- There is a small difference in the implementation described in the paper. There is no exponential interval partition before applying the recursive algorithm on each interval. A careful analysis shows the running time is the same.
- It should be clear the algorithm is not practical at all.
- Some engineering is possible. For example, in lower levels of the recursion, use the O(nu) time algorithm instead.
- This randomized algorithm by Karl Bringmann might be more practical.