# Runtime of enumerating all integer vectors with a given sum where every element is greater than sqrt(k)

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?

• I think you're not interested so much in the runtime, but rather in the number of such sequences. Jul 27 at 17:26

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.
• they are called compositions of $m$ in combinatorics parlance Jul 27 at 20:11