Combinatorics Coding Problems: 25 Questions with Solutions
25 combinatorics coding problems — 2 easy · 10 medium · 13 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 25
- By difficulty: 2 easy · 10 medium · 13 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Combinatorics counts arrangements without listing them: paths through a grid, orderings of letters with repeats, ways to split a number or to schedule a set of tasks. The tools are few — the product rule, binomial coefficients, factorials divided by the repeats they overcount, and recurrences that build the count for n from smaller counts. The problems here practise turning a story into one of those forms, and computing a result that runs to hundreds of digits modulo a large prime.
How combinatorics works, step by step
n = 6, k = 2- C(n, k) counts the ways to choose k items from n. Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k) builds each row from the one above — the last item is either taken or left out. Row 0 is just C(0, 0) = 1.
- Row 1 is 1, 1. An entry at the edge has only one parent above it — the missing one counts as 0 — so every row starts and ends with 1.
- Row 2 is 1, 2, 1. C(2, 1) = 1 + 1 = 2: item 2 is either taken (C(1, 0) = 1 way to pick the rest) or left out (C(1, 1) = 1 way).
- Row 3 is 1, 3, 3, 1. C(3, 2) = 2 + 1 = 3, and the row is symmetric: choosing 2 items to take is choosing 1 to leave, so C(3, 2) = C(3, 1).
- Row 4 is 1, 4, 6, 4, 1. C(4, 2) = 3 + 3 = 6. The row adds up to 16 = 2⁴: every subset of 4 items is counted once, by its size.
- Row 5 is 1, 5, 10, 10, 5, 1. C(5, 2) = 4 + 6 = 10. Each entry costs one addition and stays a small integer, with no factorials to overflow.
- Row 6 is 1, 6, 15, 20, 15, 6, 1. C(6, 2) = 5 + 10 = 15. Only the previous row is ever read, so one array of length n + 1, updated right to left, is enough.
- C(6, 2) = 15: there are 15 ways to choose 2 items from 6. Building rows 0 to n costs O(n²) additions — O(n × k) if only columns 0 to k are kept — and uses no division, so it works under any modulus.
Combinatorics study plan
12 of the 25 Combinatorics problems (2 easy, 7 medium and 3 hard) over 8 days, about 7 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 13 in the full list below are practice at your own pace. Then move on to Trees.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Unique Paths Medium
- Count Sorted Vowel Strings Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Find the N-th Value After K Seconds Medium
- Number of Ways to Reach a Position After Exactly k Steps Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Vowels of All Substrings Medium
- Ugly Number III Medium
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Count Anagrams Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Combinatorics: the essentials
When to reach for it
"How many ways", "how many distinct arrangements", and nearly always "modulo 10⁹ + 7": far too many to list, so the count comes from a formula or a recurrence. Independent choices multiply; positions picked from a set are a binomial coefficient; a bag of items put in order is a multinomial.
The pattern
Match the objects one to one with something standard. A right-or-down path through an m × n grid is a sequence of m − 1 downs and n − 1 rights: C(m + n − 2, m − 1) paths. A word's orderings are n! divided by the factorial of each letter's count. Under a prime modulus p, divide by multiplying with the inverse pow(x, p - 2, p) (Fermat's little theorem). Failing a formula, a Dynamic Programming recurrence counts.
def make_choose(n, mod=10**9 + 7): # C(a, b) % mod for 0 <= a <= n, mod prime
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % mod
inv = [1] * (n + 1)
inv[n] = pow(fact[n], mod - 2, mod) # Fermat: x^(p-2) is 1/x mod p
for i in range(n, 0, -1):
inv[i - 1] = inv[i] * i % mod
def choose(a, b):
return 0 if b < 0 or b > a else fact[a] * inv[b] % mod * inv[a - b] % mod
return choose
Cost
O(n) to build the tables, then O(1) per binomial. Pascal's rule — each entry the sum of the two above it — fills an O(n × k) table with no division, for a non-prime modulus.
Common mistakes
- Dividing after reducing:
(a % p) / bis not(a / b) % p; multiply by the inverse. - Overflow: two residues below 10⁹ + 7 multiply to about 10¹⁸, beyond 32 bits. Reduce after every product.
- Counting one arrangement twice: ordered where the question is unordered, or identical items treated as distinct.
- Off-by-one formulas (m − 1 moves down, not m); check each against brute force on tiny inputs.
Start with
- Sum of All Subset XOR Totals: a bit set in any element is set in half the subset XORs.
- Unique Paths: a path as a choice of positions.
- Count Anagrams: factorials over repeated letters, modulo a prime.
All combinatorics problems
Easy (2)
- Prime Arrangements Math
- Sum of All Subset XOR Totals Array, Math, Backtracking
Medium (10)
- Number of Strings Which Can Be Rearranged to Contain Substring Math, Dynamic Programming
- Find All Possible Stable Binary Arrays I Dynamic Programming, Prefix Sum
- Number of Sets of K Non-Overlapping Line Segments Math, Dynamic Programming
- The k-th Lexicographical String of All Happy Strings of Length n String, Backtracking
- Ugly Number III Math, Binary Search, Number Theory
- Vowels of All Substrings Math, String, Dynamic Programming
- Number of Ways to Reach a Position After Exactly k Steps Math, Dynamic Programming
- Find the N-th Value After K Seconds Array, Math, Simulation
- Count Sorted Vowel Strings Dynamic Programming, Math
- Unique Paths Math, Dynamic Programming
Hard (13)
- Find the Count of Monotonic Pairs I Array, Math, Dynamic Programming
- Kth Smallest Instructions Array, Math, Dynamic Programming
- Numbers With Repeated Digits Math, Dynamic Programming, Digit DP
- Poor Pigs Math, Dynamic Programming
- Student Attendance Record II Dynamic Programming
- Count Ways to Make Array With Product Array, Math, Dynamic Programming
- Count the Number of Ideal Arrays Math, Dynamic Programming, Number Theory
- Number of Ways to Rearrange Sticks With K Sticks Visible Math, Dynamic Programming
- Number of Ways to Reorder Array to Get Same BST Array, Math, Divide and Conquer
- Count All Valid Pickup and Delivery Options Math, Dynamic Programming
- Count Special Integers Math, Dynamic Programming
- Count Anagrams Hash Table, Math, String
- Number of Music Playlists Math, Dynamic Programming
Companies that ask combinatorics problems
- Amazon 22 problems on combinatorics
- Google 20 problems on combinatorics
- Adobe 4 problems on combinatorics
- Microsoft 4 problems on combinatorics
- Meta 3 problems on combinatorics
- Uber 2 problems on combinatorics
- MathWorks 1 problem on combinatorics
- Ola 1 problem on combinatorics
- Razorpay 1 problem on combinatorics
- Spotify 1 problem on combinatorics
- Zoho 1 problem on combinatorics
Next topic: Trees