During my quest to become pupil (which requires learning FFT) I discovered how to do the classic subset sum problem using FFT. As you all know, FFT is an algorithm commonly used for polynomial multiplication. What does it have to do with calculating subset sums though? (all you need to know about FFT for this blog is that it is used for multiplying polynomials)
Let's look at the dp solution first. While considering a number, you can either use it or not use it. If a number can be used an arbitrary amount of times (which is the constraint the blog will be focusing on from now on), it can either be used $$$0$$$ times, once, twice, ... This can be represented as a polynomial.
The polynomial for a number $$$n$$$ will look like: $$$1 + z^n + z^{2n} + z^{3n} + ...$$$
What does this have to do with subset sums though? You can first get rid of some terms in the polynomial, i.e. the terms with exponents greater than $$$x$$$, the target sum. When multiplying $$$2$$$ such polynomials, a lot of stuff happens, to say the least. But, because $$$2$$$ polynomials are being multiplied, both with the same bases, some exponents are going to be added to some other exponents.
This might sound confusing but to clear it up let's look at $$$2$$$ polynomials of numbers $$$a$$$ and $$$b$$$.
In simple terms, this means to make an arbitrary sum using the $$$2$$$ numbers, we can use $$$b$$$ $$$0$$$ times, once, twice, ... and combine it with the number $$$a$$$, which we can also use $$$0$$$ times, once, twice, ... Does this sound familiar? This is the subset sum problem! This interesting property is not restricted to polynomials with only $$$1$$$ and $$$0$$$ in their coefficients. So this means that we can compute ways to construct sums of $$$n$$$ numbers using polynomial multiplication, which can be done with FFT. Because we got rid of the terms with exponents greater than $$$x$$$, we will need to do polynomial multiplication with $$$n$$$ polynomials of length $$$x$$$. In the final polynomial, you can find the number of ways to construct a sum $$$x$$$ by just looking at the coefficient of the $$$z^x$$$ term. All of this can be done in $$$O(n x \log x)$$$.
Sadly, the "naive" FFT solution is slower than the dp solution in $$$O(nx)$$$. This trick though isn't that unknown, -is-this-fft- used it as an example of what FFT can be used for in his FFT tutorial. I would also implement this as a proof it works, but I couldn't find any problems which have low enough constraints for this method to pass.
