Constant term of generating function to solve special case of Subset Sum Problem

Question

Let the set $S = \{ -n,-n+1,-n+2,\dotsc,-1,0,1,2,\dotsc,n \}$. I want to find the total number of subsets whose sum is equal to 0. There is a simple $O(n^3)$ Subset Sum Problem DP solution that can do the job quite well.

However, I mentioned this problem to my friend and he defined it in terms of generating functions, namely $$\mathcal{G}(x) = \prod_{k=-n}^n \left(1 + x^k\right)$$ and the constant term of $\mathcal{G}(x)$ has the answer.

I stuck it into Wolfram and it gave me the q-Pochhammer symbol. I was thinking, is it possible to do this in $O(n^2 \log n)$ using a FFT? The only issues I see with this is that $\mathcal{G}(x)$ isn't actually a polynomial and querying $O(n^2)$ points to use an IFFT (if that's the method used) takes $O(n^3)$ time.

Regardless, if there exists a closed form/faster way of computing the constant term, I'd love to know about it!

Answer 1

Okay, so I think I got an $O(n^2 \log^2(n))$ algorithm, thanks to @AlexanderBurstein and the OEIS link.

The idea is to use the formulation (in the OEIS link) that the constant term of $\mathcal{G}(x)$ is equivalent to twice the sum of squares of coefficients of $\mathcal{H}(x) = \prod\limits_{k=1}^n. (1+x^k)$.

So, this can be done by considering each polynomial as a leaf in a binary tree. We then multiply two polynomials (binomials at the leaf stage) at a time, represented by the merging of two leaf nodes into a single node one level up the tree.

In this example, I'm assuming $n = 8$, a clean power of 2. I'm also using upper bounds for the degree at each node above the first layer. So, there are $\frac{n}{2}$ multiplications from $1 \to 2$, each of degree $2n$, so the overall cost of $1 \to 2$ is $\frac{n}{2} \cdot 2n \log_2(2n)$.

The cost from $2 \to 3$ is $\frac{n}{4} \cdot 4n \log_2(4n)$, and so on. It's clear that each layer's cost will be bounded by $n^2 \log_2(n^2)$, and since there are $\log_2(n)$ layers of this binary tree, the overall upper bound complexity will be $O(n^2 \log_2(n^2) \log_2(n)) = \boxed{O(n^2 \log^2(n))}$

Reading the coefficients and computing the answer can be resolved with a simple linear scan over the $O(1 + \frac{n(n+1)}{2})$ coefficients, which doesn't change the aforementioned time complexity.

Answer 2

Finding a single solution with complexity equal or smaller than $O(n^{2-\epsilon})$ and whose cardinality is 3 (i.e., restricted to 3 element subsets) is equivalent to solving a version (supported on $[-n,n] \cap \mathbb{Z}$) of the 3-SUM problem, which would be a big breakthrough.