A Faster Pseudopolynomial Time Algorithm for Subset Sum

Author here. The idea is a mix of many things. This is not how we write it in the paper, but just for intuition.

If Σ(S) is the set of all subset sums of S, where S={s_1,...,s_n}, then

Σ(S) = Σ(s_1)+Σ(s_2)+...+Σ(s_n).

Here A+B = {a+b|a in A, b in B} + is associative and commutative. Now we want to add parenthesis on that formula in a way such that it is fast. Similar to matrix chain multiplication. We make sure + can be fast if certain property are satisfied(Theorem 2), and the rest is just figuring out the right way to add parenthesis.