AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Combinatorics coding problems

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.

25 problems · 2 easy · 10 medium · 13 hard · judged by hidden tests in 13 languages

25problems

2 easy

10 medium

13 hard

Sign in to tick off what you solve.

Study plan: 12 problems · about 7 h 30 min

Start the study plan

Next up: Sum of All Subset XOR Totals

How it works

Combinatorics, step by step

Binomial coefficients C(n, k), with Pascal's triangle

n = 6, k = 2

n = 01C(n, k) = C(n − 1, k − 1) + C(n − 1, k)

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.

0:01 / 0:28Step 1 of 8
Transcript · 8 steps

Study plan

Learn combinatorics in 8 days

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.

  1. Day 1

    about 55 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

  2. Day 2

    about 1 h 10 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 35 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Trees

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 = 01n = 111n = 2121n = 31331n = 414641n = 515101051n = 61615201561C(6, 2) = 15
Binomial coefficients C(n, k), with Pascal's triangle. Example: n = 6, k = 2
  1. 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.
  2. 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.
  3. 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).
  4. 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).
  5. 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.
  6. 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.
  7. 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.
  8. 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.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

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.

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.

Next topic: Trees

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) / b is 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

All combinatorics problems

Easy (2)

Medium (10)

Hard (13)

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