Combinatorics for Coding Interviews: DSA Guide

Combinatorics answers “how many ways” without enumerating the ways.

Two tools cover almost everything:

Pascal’s rule: C(n,k) = C(n−1,k−1) + C(n−1,k) — build a table when n is small. Factorial formula: C(n,k) = n! / (k!(n−k)!) — use factorials + inverses mod p when n is large.

Focus on recognizing:

“How many ways to choose/arrange” = nCr or nPr — never brute force

Pattern 1: Pascal’s Triangle (small n)

Watch Pascal’s rule assemble the triangle — every interior cell is the sum of its two parents. Press ▶ to animate.

Pascal's Triangle

Build Pascal's triangle; each cell is the sum of its two parents above.

Edges C(n,0)=C(n,n)=1. Interior cells C(n,k)=C(n-1,k-1)+C(n-1,k) (Pascal's rule). The triangle gives binomial coefficients; row sums are powers of two. O(n²) time and space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        C(n, 0) = C(n, n) = 1                    // edges
                      
                        2
                        C(n, k) = C(n-1, k-1) + C(n-1, k)        // Pascal's rule
                      
                        3
                        closed form: C(n,k) = n! / (k! (n-k)!)
                      
                        4
                        mod p: divide by multiplying the modular inverse

public long[][] pascal(int n) {
    long[][] c = new long[n + 1][];
    for (int i = 0; i <= n; i++) {
        c[i] = new long[i + 1];
        c[i][0] = c[i][i] = 1;
        for (int k = 1; k < i; k++)
            c[i][k] = c[i - 1][k - 1] + c[i - 1][k];
    }
    return c;
}

def pascal(n: int) -> list[list[int]]:
    c = []
    for i in range(n + 1):
        row = [1] * (i + 1)
        for k in range(1, i):
            row[k] = c[i - 1][k - 1] + c[i - 1][k]
        c.append(row)
    return c

vector<vector<long long>> pascal(int n) {
    vector<vector<long long>> c;
    for (int i = 0; i <= n; i++) {
        c.emplace_back(i + 1, 1);
        for (int k = 1; k < i; k++)
            c[i][k] = c[i - 1][k - 1] + c[i - 1][k];
    }
    return c;
}

function pascal(n) {
  const c = [];
  for (let i = 0; i <= n; i++) {
    const row = Array(i + 1).fill(1);
    for (let k = 1; k < i; k++)
      row[k] = c[i - 1][k - 1] + c[i - 1][k];
    c.push(row);
  }
  return c;
}

Pattern 2: nCr mod p (large n)

Precompute factorials and inverse factorials once; each query is O(1):

static final long MOD = 1_000_000_007L;

public long nCr(int n, int r, long[] fact, long[] invFact) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

// precompute:
// fact[0] = 1; fact[i] = fact[i-1] * i % MOD
// invFact[n] = power(fact[n], MOD - 2);
// invFact[i] = invFact[i+1] * (i+1) % MOD   (walk backwards)

MOD = 1_000_000_007

def precompute(n: int):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD

    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD
    return fact, inv_fact

def n_cr(n: int, r: int, fact, inv_fact) -> int:
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

const long long MOD = 1'000'000'007LL;

long long nCr(int n, int r,
              vector<long long>& fact, vector<long long>& invFact) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

// precompute:
// fact[0] = 1; fact[i] = fact[i-1] * i % MOD
// invFact[n] = power(fact[n], MOD - 2);
// invFact[i] = invFact[i+1] * (i+1) % MOD   (walk backwards)

const MOD = 1_000_000_007n;

function nCr(n, r, fact, invFact) {
  if (r < 0 || r > n) return 0n;
  return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

// precompute:
// fact[0] = 1n; fact[i] = fact[i-1] * BigInt(i) % MOD
// invFact[n] = power(fact[n], MOD - 2n);
// invFact[i] = invFact[i+1] * BigInt(i+1) % MOD

Small n → Pascal table. Large n → factorials + inverse factorials.

Common Mistakes

Forgetting r > n guard.

C(n, r) with r > n must be 0 — the formula silently returns garbage otherwise.

Dividing factorials directly.

Division doesn’t exist mod p — multiply by modular inverses (previous lesson).

Overflow before %.

Chain multiplies left-to-right reducing after each step: a * b % MOD * c % MOD, not (a * b * c) % MOD on wide values.

Complexity

Approach	Build	Query
Pascal table	O(n²)	O(1)
Factorials mod p	O(n)	O(1)

⚠️ Animation & Content Notice

Combinatorics

Pattern 1: Pascal’s Triangle (small n)

⚠️ Animation & Content Notice

Pascal's Triangle

Pattern 2: nCr mod p (large n)

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern 1: Pascal’s Triangle (small n)

Pascal's Triangle

Pattern 2: nCr mod p (large n)

Common Mistakes

Complexity

Premium Content

My Private Notes