Foundations
Combinatorics basics
Permutations n!, combinations, subsets 2ⁿ - visualized with small n.
Question: how many operations to enumerate all subsets of 20 items?
2²⁰ = 1,048,576. Survivable. But 30 items is 2³⁰ ≈ 10⁹ and you're guaranteed to time out. This page unpacks the gap between n!, 2ⁿ, and C(n,k) and where each one drives a DSA pattern.
By the numbers
| n | 2ⁿ | C(n, n/2) | n! | Judge limit (≈10⁸) |
|---|---|---|---|---|
| 10 | 1,024 | 252 | 3.6M | survives |
| 15 | 32,768 | 6,435 | 1.3T | 2ⁿ ok, n! dies |
| 20 | 1M | 184,756 | 2.4·10¹⁸ | 2ⁿ ok, n! impossible |
| 25 | 33M | 5.2M | blows up | 2ⁿ tight, C(n,k) ok |
| 30 | 1.07B | 155M | blows up | 2ⁿ dies, C(n,k) tight |
One line: 2ⁿ survives for n ≤ 20, dies for n ≥ 30. n! is already impossible at n ≥ 15. C(n, k) at k ~n/2 is ~√(πn/2) smaller than 2ⁿ but still exponential.
Where each comes from
n! (permutations)
n items: first has n positions, second n-1, … → n · (n-1) · … · 1 = n!. Enumerating all permutations (LC 46, 47) costs this. Backtracking in its naive form is exactly this; without pruning you walk every leaf.
2ⁿ (subsets)
Each item is included or excluded, two choices → 2 · 2 · … · 2 = 2ⁿ. Enumerating all subsets (LC 78, 90) or subset DP (LC 416, 494) costs this. n ≤ 20 gives ~1M leaves you can actually walk; that's why subset DP has the n ≤ 20 rule.
C(n, k) (combinations)
Choose k from n: n! / (k! · (n-k)!). Generating combinations (LC 39, 77) produces this many leaves. Maximized at k ~n/2, where it's ~2ⁿ / √(πn/2): smaller than 2ⁿ but still exponential.
Trap: "C(n, k) is polynomial, 2ⁿ is exponential"
Wrong. C(n, n/2) is exponential: C(20,10) = 184,756,C(30,15) = 155M. For fixed k, C(n,k) = O(nᵏ) is polynomial, but if k grows with n it's exponential. So "combinations are polynomial" is misleading; it depends on how k relates to n.
Where to go next
- Growth rates - 2ⁿ and n! next to the other bounds.
- LC 46 Permutations - where n! is born.
- LC 78 Subsets - where 2ⁿ is born.
- LC 39 Combination Sum - C(n,k) backtracking.
- LC 416 Partition Equal Subset Sum - subset DP, n ≤ 200 not 2ⁿ.
Exercise
Set the slider to n = 10. Predict the n!, 2ⁿ, and C(n, n/2) values. Now move ton = 15: how many times did n! grow? How many times did 2ⁿ? This concretizes why backtracking problems carry n ≤ 15 constraints.