A combinatorial explosion occurs when the number of possible solutions (the search space) grows exponentially or factorially with the size of the input, making exhaustive search completely infeasible.
KEY TAKEAWAY: Combinatorial explosions render brute-force approaches computationally intractable even for moderate input sizes. Recognising when an explosion will occur is essential before choosing a search strategy.
Combinatorial explosions arise from:
| Source | Growth Rate | Example |
|---|---|---|
| Binary choices (include/exclude) | $2^n$ | Subsets, 0-1 Knapsack |
| Orderings / permutations | $n!$ | TSP routes, assignment |
| Combinations | $\binom{n}{k}$ | Selecting $k$ items from $n$ |
| Decision tree branching | $b^d$ ($b$ = branching factor, $d$ = depth) | Game trees |
| $n$ | $2^n$ | $n!$ |
|---|---|---|
| 10 | 1,024 | 3,628,800 |
| 20 | 1,048,576 | \$2.4 \times 10^{18}$ |
| 30 | 1,073,741,824 | \$2.65 \times 10^{32}$ |
| 50 | $10^{15}$ | \$3 \times 10^{64}$ |
For $n = 30$: $2^{30} \approx 10^9$ — a fast computer ($10^9$ ops/sec) would take ~1 second. But $n = 100$: $2^{100} \approx 10^{30}$ — longer than the age of the universe.
Look for these problem features:
| Indicator | Explanation |
|---|---|
| “All subsets” | $2^n$ subsets of $n$ items |
| “All orderings/routes” | $n!$ permutations |
| “Best combination of items” | Combinatorial search |
| “Satisfy all constraints” | Constraint satisfaction (SAT, colouring) |
| “Visit every node exactly once” | Hamiltonian path/TSP |
| “Assign tasks to workers optimally” | Assignment problem |
| Decision tree with large branching factor | Exponential in depth |
When a problem exhibits a combinatorial explosion:
EXAM TIP: A common exam question asks you to “explain why a brute-force approach is not feasible” for a given problem. Quantify: how many possibilities are there? How does this grow with $n$? What would the running time be in practice?
