BigBadBully's blog

Subset sum with FFT
By BigBadBully, history, 16 months ago, In English

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$$$.

$$$a(z) = 1 + z^a + z^{2a} + ...$$$
$$$b(z) = 1 + z^b + z^{2b} + ...$$$
$$$a(z) \cdot b(z) = a(z) \cdot 1 + a(z) \cdot z^{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.

  • Vote: I like it
  • -19
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

why did i get -5 i've had enough i'm qutting cp now i become a professional skydiver because i've been bullied too much

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is stupid. Why don't you do something productive instead of learning advanced algorithms, such as maybe doing more problems?

→ Reply
»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

why ami getting so much downvotes bruhh

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You are right, FFT may be used for that, if you may take $$$b$$$ elements while choosing out of $$$n$$$ types suppose that we have infinite amount of each item,the question is how many are there possible ways to get sum $$$W$$$, then the solution would be to first construct a polinomial in which coeficient $$$k$$$ is the number of elements in initial array that have the value $$$k$$$, and after that you would have to raise this polinomial to the $$$b$$$-th power I think that proof of that I am not ready to explain in English, in a total time complexity of $$$O(biggest_element*b*log(biggest_element*b)*log(b))$$$ using FFT (the actual FFT, not the ordinary FT (fourier transform)). please correct me if I am wrong, sometimes i mess up with time complexity

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually I think that it would be a great idea to post some math solutions to the problems (using FFT or matrix multiplication)

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't quite understand what you wanted to say, but this blog was written for the version of the problem in which we have infinite amounts of each item. But, if we have a limited amount of each item then we can build a frequency array (or map) of each item. We will calculate the polynomial based on the frequency array then. If $$$a$$$ is the freq array (or map) then the polynomial for $$$a_i$$$ is:

    $$$p_i(z) = 1 + z^{i} + z^{2i} + ... + z^{i\cdot a_i}$$$

    From now on, the solution is pretty much the same.

    → Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I am incredulous about the way you have defined these things. Are you sure you aren't just being pompous here? Such bogs are vile to the succinct resources I have prepared in the past

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"become pupil requires learning FFT"

→ Reply