Is summing over all possible $k$-combinations NP-hard?
You can compute the coefficient of $x^k$ in
$$ \prod_{i=1}^n (1+xa_i). $$
Alternatively, you can think of this as a dynamic programming algorithm. Let $b(m,\ell)$ be the sum of $\ell$-combinations of $a_1,\ldots,a_m$. We have
$$ b(m,\ell) = b(m-1,\ell) + a_m b(m-1,\ell-1), $$
where $b(m,-1) = 0$, $b(0,0) = 1$, and $b(0,\ell) = 0$ for $\ell \neq 0$. What you want is $b(n,k)$.

In both cases, there is an optimization that only keeps track of $\ell$-combinations for $\ell \leq k$. In the polynomial representation, it is enough to keep the monomials up to $x^k$. In the dynamic programming approach, we only compute the table up to $b(m,k)$.