Subarrays, Subsequences, Subsets, Combinations & Permutations - Math Cheat Sheet
Subarrays, Subsequences, Subsets, Combinations & Permutations - Math Cheat Sheet
If you’ve ever mixed up “subsequence” with “subset” during an interview or debugging session, you’re not alone. These terms get thrown around constantly in coding interviews, LeetCode problems, and algorithm discussions — and the differences are subtle but critical.
Here’s the ultimate comparison table that I wish I had taped above my monitor years ago.
The Ultimate Summary Table
| Term | # Elements | Order Preserved? | Contiguous? | Total Count |
|---|---|---|---|---|
| Subarray / Substring | 0 to n | Yes (exact original order) | Yes | n(n+1)/2 + 1 (incl. empty) |
| Subsequence | 0 to n | Yes (relative original order) | No (can skip) | 2ⁿ (incl. empty) |
| Subset | 0 to n | No (order irrelevant) | No | 2ⁿ (incl. empty set) |
| Combination | exactly k | No (order irrelevant) | No | C(n,k) = n! / (k!(n−k)!) |
| Permutation / k-Permutation | n (or exactly k) | Yes (order matters, all distinct) | No | n! or P(n,k) = n! / (n−k)! |
Quick Rules of Thumb (The 3 Key Differences Everyone Gets Wrong)
| Comparison | The Crucial Difference |
|---|---|
| Subarray vs Subsequence | Subarray = contiguous block Subsequence = can skip elements |
| Subsequence vs Subset | Subsequence respects relative order Subset doesn’t care about order at all |
| Subset vs Combination | Subset = any size (0 to n) Combination = fixed size k only |
Real Example with [1, 2, 3]
| Type | All Possible Results |
|---|---|
| Subarrays (must be contiguous) | [], [1], [2], [3], [1,2], [2,3], [1,2,3] |
| Subsequences (order preserved, can skip) | [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] ✓ [1,3] is valid ✗ [3,1] is not (breaks order) |
| Subsets (order doesn’t matter) | {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} |
| Combinations (k=2) | {1,2}, {1,3}, {2,3} |
| Permutations (full n=3) | [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] |
One-Liner to Remember Forever
“Subarray = slice of cake (contiguous) Subsequence = picking some cherries while keeping their left-to-right order Subset = throwing cherries into a bowl (order doesn’t matter) Combination = picking exactly k cherries for a recipe Permutation = arranging the cherries in a line — every different order counts”
Drop this table. You’ll look like a wizard.