The problem of enumerating all lists of integers such that the list sums to a known value $k$ is well known and takes exponential time to compute.
If the problem is restricted so that the integers must be greater than $\sqrt{k}$, I feel like the runtime should now be quadratic. Is there a proof of this? More generally, if I restrict the integers to be greater than $l$, how is the runtime affected?
The number of sequences of non-negative integers of length $\ell$ summing to $m$ is $\binom{m+\ell-1}{\ell-1}$. This shows that the number of sequences of integers, each at least $t$, summing to $k$ is $$ \sum_{\ell=1}^{\lfloor k/t \rfloor} \binom{k-\ell t}{\ell - 1}. $$ For example, if $t = \lfloor \sqrt{k}+1 \rfloor$, then we can choose $\ell \approx \sqrt{k}/2$ to get at least $\binom{\Theta(k)}{\Theta(\sqrt{k})}$ many sequences, which is $\exp \Theta(\sqrt{k} \log k)$; this is tight up to the hidden constant.
