Subarrays, Subsequences, Subsets, Combinations & Permutations - Math Cheat Sheet
0:000:00
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.