Combinatorial explosion

A combinatorial explosion is a rapid increase in the number of candidates generated by a search over combinations, often exponential or factorial in an input parameter. For example, listing all subsets of an $n$-element set produces $2^n$ candidates, while listing all permutations produces $n!$ candidates. In contrast, listing only fixed-size $q$-element subsets has time complexity at least $\left(\genfrac{}{}{0ex}{}{n}{q}\right)=\Theta (n^q)$ for fixed $q$: potentially large, but polynomial rather than exponential in $n$.