Skip to main content
1 of 2

Number of subset sums

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, 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$?