Let $\mathbb{F}\_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}\_q$ be a some set with $|D|=n$. Find a non-empty subset $\{x\_1,\dots,x\_k\} \subseteq D$ such that $x\_1+\cdots+x\_k=s$ for some given $s\in\mathbb{F}\_q$. This is the definition of the subset sum problem.


What I cannot understand is how do you count the number of solutions for a given $s$. In this [paper](http://arxiv.org/abs/0708.2456), in page 2 it says 



> 
> heuristically should be approximately $\frac{1}{q}\binom{n}{k}$.
> 
> 
> 


A more concrete questions is, given $s$ how many summands does it have given that we select $D$ randomly from $\mathbb{F}\_q$?



Number of subset sums
There are $\binom{n}{k}$ ways to choose $k$ elements from $n$ elements. If we consider their sum it is "expected" to be equal to every element of the field with the same probability. Hence we get $\frac{1}{q}\binom{n}{k}$ for the number of solutions of $x\_1 + x\_2 + \cdots + x\_k = s$. This is the first part of your question.


Now there are $\binom{q}{k}$ ways to choose $k$ different elements of the field. And $\frac{1}{q}$ of them have sum equal to $s$. In other words number of solutions of $x\_1 + x\_2 + \cdots + x\_k = s$ is equal to $\frac{1}{q}\binom{q}{k}$.


If we choose random $D$ with $|D|=n$ every solution will have all $x\_i \in D$ with the same probability $p$:


$$p = \frac{\binom{q-k}{n-k}}{\binom{q}{n}}$$


Hence the expected number of solutions is equal to $\frac{1}{q}\binom{q}{k} \cdot p$ which is equal to $\frac{1}{q}\binom{n}{k}$.


So the expected number of solutions is equal to $\frac{1}{q}\binom{n}{k}$.


