= Solution
The number is
$$
\boxed{\binom{16}{6}=8008.}
$$
A direct search over every $q$-element <subset> must inspect $\binom nq$ candidates. Testing one candidate by generating its <subset sums> creates $2^q$ values; storing previously seen sums detects a collision. Generating them incrementally needs $O(2^q)$ arithmetic operations, or $O(q2^q)$ for the straightforward independent calculation of each sum. Thus the simple overall search has cost on the scale of $\binom nq2^q$, apart from <integer>-arithmetic and data-structure costs.
The important <time complexity> distinction is that \b[fixed $q$ gives polynomial growth in $n$, of degree $q$], but this can still become impractically large. If $q$ increases with $n$, both the candidate count and the internal <power set> can grow exponentially. For example, near $q=n/2$ the <binomial coefficient> is already exponentially large. An exhaustive implementation can therefore encounter a <combinatorial explosion>; the fixed-$q$ estimate $\Theta(n^q)$ must not be described as exponential in $n$.
Back to article page
