Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$. Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$). We want to compute the following expression:

$$ \sum_{A\in {S \choose k}} \prod_{x \in A} x$$

Is there an algorithm for this problem that works much better than the trivial one which goes over all subsets and computing and summing up all products?

share|cite|improve this question
It is very unclear what you mean, but maybe you are looking for this:'s_identities – Sasho Nikolov Jun 18 '14 at 18:54
@Kaveh: I tried to edit the wording to clarify what I am looking for. This should be something rather basic math, I am sure. – Alexander Galkin Jun 18 '14 at 19:38
@Kaveh: Great, thank you a lot!! – Alexander Galkin Jun 18 '14 at 20:03
You are asking for an efficient way to evaluate a specific multivariate symmetric polynomial at a specific input. There's lots known about symmetric polynomials; that might help you find a good solution. – D.W. Jun 18 '14 at 21:24
Sum of all nonempty subset products? Dynamic programming. SubSum(N) = $s_{n}$ * SubSum(N-1) + SubSum(N-1) + $s_{n}$ – Chad Brewbaker Jun 21 '14 at 20:26
up vote 10 down vote accepted

Consider the polynomial $p(t) = \prod_{i=1}^n (s_i t + 1)$. Then we want to compute the coefficient of $t^k$ in $p(t)$. We can compute $p(t)$ using fast polynomial multiplication and then output the coefficient of $t^k$.

Say, partition $n$ polynomials $s_i t + 1$ into pairs and multiply the product of polynomials in each pair (using the standard fast polynomial multiplication algorithm). Then divide the obtained $n/2$ polynomials into pairs, and compute the product in each pair. Repeat this step over and over until we get one polynomial. At each step we can get rid of terms of degree higher than $k$.

Also note that if $k$ is small, we can just use dynamic programming.

share|cite|improve this answer

I guess the following trick is essentially "Newton's identities", but this seems a much more straightforward application to your question than what's on the wikipedia page. I've seen this mentioned on before but don't know of a particular reference.

First, we write down the polynomial $$ p(x) = \prod_{i=1}^n (x + s_i) . $$

By simply multiplying out this polynomial (efficiently! it is $n$ products of degree $\leq n$ polynomials), we can write it as $$ p(x) = \sum_{j=1}^n \alpha_j x^j. $$ where $\alpha_j$ is the sum of all coefficients of $x^j$, that is, all possible products of $n-j$ of the $s_i$s. In particular, $$ \alpha_{n-k} = \sum_{A \in {S \choose k}} \prod_{s \in A} s .$$

share|cite|improve this answer
This is typically credited in the TCS literature to Ben-Or, viz. the private communication from Ben-Or to Nisan & Wigderson cited in "Lower bounds on arithmetic circuits via partial derivatives." – Joshua Grochow Jun 18 '14 at 22:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.