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 -element set produces candidates, while listing all permutations produces candidates. In contrast, listing only fixed-size -element subsets has time complexity at least for fixed : potentially large, but polynomial rather than exponential in .
