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 :)

  • 1
    $\begingroup$ You should be able to cancel out sums in which elements are used multiple times. This will require some case analysis, but sounds completely feasible. $\endgroup$ Oct 27 '19 at 13:25
  • $\begingroup$ It was easy for $k=2$ but I couldn't find a formula in general. maybe that is why $k$ is always small and I have to do it by hand. $\endgroup$ Oct 27 '19 at 13:36

You already explained what to do when $k = 2$. Let's see what to do when $k = 3$. Let $P_i$ be the polynomial corresponding to $iS$ (for example, the solution for $k = 2$ is $(P_1^2 - P_2)/2$).

We can construct the following table: $$ \begin{array}{c|ccc} & aaa & aab & abc \\\hline P_1^3 & 1 & 1 & 1 \\ 3P_2 P_1 & 3 & 1 & 0\\ P_3 & 1 & 0 & 0 \end{array} $$ So the solution for $k = 3$ is $(P_1^3 - 3P_2P_1 + 2P_3)/6$.

More generally, the solution will involve terms corresponding to all partitions of $k$. The coefficients presumably appear in some change-of-basis formula for symmetric polynomials, and you can find formulas by browsing monographs on the subject.

  • $\begingroup$ It seems to work with this formula $\rho_i = \frac{1}{i}\sum\limits_{j=1}^i -1^{j-1}\rho_{i-j} P_j$, where $\rho_i$ is the answer for $k = i$ $\endgroup$ Oct 27 '19 at 23:09
  • $\begingroup$ It worked!! thank you :D $\endgroup$ Oct 27 '19 at 23:55

Your Answer

