Polynomial multiplications and counting

Question

I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically speaking $$S = \{s ; \text{ there exists } P \in {A\choose k} \text{ such that } s = \sum_{a \in P} a\}.$$ The object of the problem is to compute $S$ and for each integer $s \in S$, we have to find how many subsets of $A$ of size $k$ there are that sum up to $s$.

The constraints: $k$ is very small (can be considered constant) and I am looking for something subquadratic in $n$.

---

I tried to formulate the problem as a polynomial multiplication problem and solve it using FFT. So I built the polynomial $\rho$ as follows. I started with $\rho = 0$ and For each element $a \in A$, I added $x^a$ to $\rho$. Now for each exponent $r$ in $\rho^k$, the coefficient represents the number of combinations of $k$ elements in $A$ that sum up to $r$. However, these combinations include using the same element more than one time and count reorderings of the same subset.

I have been trying the following ideas:

• Rebuilding my polynomial to count better.
• Build and multiply different polynomials each representing a part of the problem (with some kind of divide and conquer technique).
• Edit the polynomial resulting from the multiplication with some combinatorial argument (Subtract the numbers resulting from counting twice etc.). This helps when $\rho^2$ but could not make it work for higher values of $k$.

I appreciate any thoughts or hints about the problem :)