cf.completefrontend
MATH & GEOMETRY · CORE

Counting with combinations

Count the ways to choose or arrange things with formulas like C(n, k) instead of listing every way.

Time O(k) for `choose`, O(n × k) for `chooseMod`Space O(1) and O(k)6 practice problemsStep-through picture

The idea

Combinatorics is the math of counting. How many ways can you pick 2 toppings from 5? How many routes go from one corner of a grid to the other? Listing them all is slow; a formula answers at once.

The most useful formula is C(n, k), read "n choose k": the number of ways to pick k items from n when order doesn't matter. C(5, 2) = 10. It equals n! / (k! × (n - k)!), where n! means 1 × 2 × ... × n.

Factorials grow huge fast, so code computes C(n, k) carefully. One way multiplies and divides step by step with BigInt, staying a whole number at every step. Another builds Pascal's triangle, where each entry is the sum of the two above it, and works well when the answer is wanted modulo a number.

An everyday example

Choosing pizza toppings

A pizza place has 5 toppings and you may pick 2. You could list every pair: mushroom and olive, mushroom and pepper, and so on, getting 10. Or you can reason: 5 choices for the first topping, 4 for the second, so 20 ordered picks. But mushroom-then-olive and olive-then-mushroom are the same pizza, and each pizza was counted twice, so 20 / 2 = 10. That reasoning is the C(n, k) formula.

How the example maps to the code
In the exampleIn the code
The toppings on the menun
How many toppings you pickk
Ordered picks, then removing repeated ordersresult * (n - k + i) / i, one step at a time
Building a table of answers for smaller menusPascal's triangle in chooseMod

From the slow way to counting with combinations

  1. Start with the obvious way: list every possible group and count them. To count the ways to pick 8 of 12 items, loop over all 2^12 = 4096 subsets and count the ones with exactly 8 items. That's fine for 12 items, but for 40 items it's about 1.1 trillion subsets, just to print one number.
  2. Count ordered picks first. The first item can be any of 12, the second any of the 11 left, and so on: picking 4 items in order gives 12 × 11 × 10 × 9 ways. Each unordered group of 4 shows up in that count once for every order of its items, 4 × 3 × 2 × 1 = 24 times. So the number of groups is 12 × 11 × 10 × 9 / 24 = 495.
  3. Computing the top and bottom separately makes huge numbers: 21! already passes 2^53. Instead, multiply one factor and divide one factor at a time. After step i, result is C(n - k + i, i), itself a count of groups and so a whole number. Every value stays as small as it can be, and BigInt keeps it exact.
  4. Two last ideas. Choosing k items to keep is the same as choosing n - k to leave out, so use the smaller of the two and save steps. And when the answer is wanted modulo a number, division doesn't work on remainders, so build one row of Pascal's triangle with additions only. The multiply-then-divide loop is choose, and the row is chooseMod.

How it works

  1. If k < 0 or k > n, there are no ways: return 0.
  2. Use k = Math.min(k, n - k), since choosing k to keep is the same as choosing n - k to leave out.
  3. Start with result = 1n.
  4. For i from 1 to k, set result = result * (n - k + i) / i. After each step, result is C(n - k + i, i), a whole number, so the division is exact.
  5. For an answer modulo mod, build one row of Pascal's triangle instead: row[j] = row[j] + row[j - 1], going right to left.
  6. Return result (or row[k]).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function choose(n, k) {
  2. if (k < 0 || k > n) return 0n;
  3. k = Math.min(k, n - k);
  4. let result = 1n;
  5. for (let i = 1; i <= k; i++) {
  6. result = (result * BigInt(n - k + i)) / BigInt(i);
  7. }
  8. return result;
  9. }
  11. function chooseMod(n, k, mod) {
  12. const row = new Array(k + 1).fill(0);
  13. row[0] = 1;
  14. for (let i = 1; i <= n; i++) {
  15. for (let j = Math.min(i, k); j >= 1; j--) {
  16. row[j] = (row[j] + row[j - 1]) % mod;
  17. }
  18. }
  19. return row[k];
  20. }

How fast it is

TimeO(k) for `choose`, O(n × k) for `chooseMod`
Extra memoryO(1) and O(k)

choose does one multiply and one divide per step, k steps. chooseMod builds n rows of k entries each, but keeps only one row in memory.

  • Best caseO(1)

    k is 0, equals n, or is out of range. The loop runs zero times and returns 1n or 0n.

  • Average caseO(k)

    One multiply and one divide per step, min(k, n - k) steps. C(52, 5) = 2598960 needs only 5 steps.

  • Worst caseO(n)

    k is about n / 2, the most steps the symmetry allows. The numbers also get longer, so each BigInt step costs a little more for big answers like C(100, 50).

Common mistakes

  • Computing n! and dividing by k! and (n - k)! with plain numbers. 21! already passes 2^53, so the result is wrong for modest inputs.
  • Dividing before multiplying: result / i * (n - k + i) can produce fractions.
  • Applying % to the step-by-step formula. Division doesn't work on remainders; use Pascal's triangle or a modular inverse.
  • Forgetting that order matters in some questions. Arranging is n!-style; choosing is C(n, k).

When to use it

Look for these clues in a problem:

  • The question asks "how many ways" and the answer is a count, not a list.
  • Order doesn't matter (choose) or does matter (arrange), and items are picked from a fixed set.
  • Grid routes that only move right and down: a route is a choice of which steps go down.
  • The answer is huge and must be returned modulo 1000000007.

Check yourself

Answer each one in your head first, then open it.

Why does choose(12, 8) only loop 4 times?

Because C(12, 8) = C(12, 4): picking 8 to keep is the same as picking 4 to leave out. The code switches k to the smaller side.

What goes wrong if each step divides before multiplying?

BigInt division drops the remainder. For C(12, 4), step 2 computes 9n / 2n = 4n instead of 4.5, and the final answer comes out as 420n instead of 495n.

Why does chooseMod update row from right to left?

Each new row[j] needs the previous row's row[j - 1]. Going right to left updates row[j] before row[j - 1] changes. Going left to right gives 1260 for C(12, 4).

How many routes go through a grid with 4 down-steps and 8 right-steps?

495, because a route is a choice of which 4 of the 12 steps go down: C(12, 4).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

choose keeps one promise: after step i, result equals C(n - k + i, i). Before the loop, i is 0 and result is 1n, and C(n - k, 0) = 1, so the promise holds.

Each step keeps it, because of the rule C(m, i) = C(m - 1, i - 1) × m / i, with m = n - k + i. The code multiplies first, so result × m is exact in BigInt, and since C(m, i) is a whole number the division leaves no remainder. When i reaches k, the promise says result = C(n, k), the answer.

chooseMod keeps a different promise: after the outer loop finishes row i, row[j] is C(i, j) modulo mod for every j up to k. Pascal's rule C(i, j) = C(i - 1, j) + C(i - 1, j - 1) needs both values from the previous row. Going right to left means row[j - 1] still holds the old row's value when row[j] is updated. Left to right would use the new value instead, and gives 1260 for C(12, 4) instead of 495.

Going deeper

3 more ideas

Why the step-by-step division never leaves a fraction

After step i, result equals C(n - k + i, i), which is a count of ways and so a whole number. Going from step i - 1 to step i multiplies by (n - k + i) and divides by i, which is exactly the rule C(m, i) = C(m - 1, i - 1) × m / i. Multiplying before dividing keeps it exact.

Grid routes as a choice

A route from the top-left to the bottom-right of a grid that only moves right or down makes r down-steps and c right-steps in some order. Picking which of the r + c steps are down-steps decides the route. So there are C(r + c, r) routes. A 3-by-3 block of moves has C(6, 3) = 20 routes.

Other counting rules worth knowing

Arrangements of n different items: n!. Arrangements of letters with repeats, like AAB: n! divided by the factorial of each letter's count, so 3! / 2! = 3. Pairs among n items: C(n, 2) = n × (n - 1) / 2. Each of n items in or out: 2^n subsets.

Work it by hand

Every step in a table, with why

Count the ways to choose 8 items from 12. The trace shows k switching to the smaller side first.

n = 12, k = 8

StepiMultiply byDivide byresultWhat happensWhy
1----0 <= 8 <= 12: continuek is in range, so the answer isn't 0.
2----k = Math.min(8, 4) = 4Choosing 8 to keep is the same as choosing 4 to leave out. 4 steps instead of 8.
3---1nresult = 1nThere is exactly one way to choose nothing, so the count starts at 1.
41919n1n × 9n / 1nn - k + i is 12 - 4 + 1 = 9. Now result is C(9, 1) = 9.
5210245n9n × 10n / 2n90 / 2 = 45, which is C(10, 2). The division comes out even.
63113165n45n × 11n / 3n495 / 3 = 165, which is C(11, 3).
74124495n165n × 12n / 4n1980 / 4 = 495, which is C(12, 4). i reaches k, so the loop ends.

It returns 495n. Every middle value was a real count, C(9, 1), C(10, 2), C(11, 3), so every division was exact. chooseMod(12, 8, 1000000007) builds Pascal's rows instead and also gives 495.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Counting with combinationsO(k)O(1)One exact answer, possibly huge, kept as a BigInt.
Pascal's triangle rowO(n · k)O(k)The answer is wanted modulo a number that may not be prime, and n is up to a few thousand.
Factorial tables with inversesO(n)O(n)Many questions modulo a prime: build the tables once, then each answer takes O(1).
Listing every subsetO(2^n)O(n)Only when you need the groups themselves, not just how many there are.

Extra memory: O(1) for choose: one BigInt, which grows with the answer's digits. chooseMod keeps one row of k + 1 numbers, O(k).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Counting with combinations and the other approaches, on a scale where each line up is 10 times more steps.
  • Counting with combinations, Factorial tables with inverses O(k)
  • Pascal's triangle row O(n · k)
  • Listing every subset O(2^n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Counting with combinations101,0001 million
Pascal's triangle row1001 million1 trillion
Factorial tables with inverses101,0001 million
Listing every subset1,024more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
k out of range: choose(3, 5) or choose(5, -1)
The first line returns 0n: there is no way to choose 5 items from 3. chooseMod(3, 5, 100) also returns 0, because row[5] is never added to.
k = 0 or k = n
After k = Math.min(k, n - k), k is 0, the loop doesn't run, and it returns 1n. There is one way to choose nothing and one way to choose everything.
n = 0, k = 0
Returns 1n: the empty group is the one way to choose from nothing.
A result past 2^53: choose(60, 30)
The BigInt result is exactly 118264581564861424n. Turning it into a plain number with Number(...) gives 118264581564861420, so keep it as BigInt or take a remainder.
Mixing types: 1 + choose(5, 2)
Throws TypeError: Cannot mix BigInt and other types. Convert on purpose with Number(choose(5, 2)) when the value is small, or add 1n instead.

Variations and follow-ups

Twists interviewers add

Factorial tables with inverses

For many C(n, k) % MOD questions, precompute fact[i] and invFact[i] up to the largest n once. Then each answer is fact[n] × invFact[k] × invFact[n - k] % MOD, in O(1). The inverses come from fast exponentiation, since MOD is prime.

Stars and bars

Putting n identical items into k boxes is the same as choosing where the k - 1 dividers go among n + k - 1 places: C(n + k - 1, k - 1). Five identical items into three boxes gives C(7, 2) = 21 ways.

Grid routes

A route that only moves right or down is a choice of which steps go down. A grid route with 4 down-steps and 8 right-steps has C(12, 4) = 495 routes, the same number as the trace.

Catalan numbers

C(2n, n) / (n + 1) counts balanced bracket strings, binary tree shapes, and many more structures. For n = 7 it is 3432 / 8 = 429.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "how many ways", "number of distinct groups", "number of paths" in a grid that only moves right and down, or a constraint like n <= 10^5 with "return the count modulo 10^9 + 7".
  • Explain the formula with the ordered-picks story: "n × (n - 1) × ... counts ordered picks, and each group appears k! times, so I divide by k!." Then say why you divide step by step.
  • Test k = 0, k = n, k > n, and a case where k > n / 2 so the symmetry line matters. Check one value against a small Pascal's triangle by hand.
  • Expect "now give it modulo 10^9 + 7". Answer that you can't divide remainders, so either build Pascal's row with additions or multiply by modular inverses from a factorial table.

Where frontend code uses it

The same idea in real UI code
  • Collision checks between n draggable items compare every pair, which is C(n, 2) = n × (n - 1) / 2 checks. Knowing that number shows why it gets slow for 1,000 items (almost 500,000 pairs).
  • Test plans that try every combination of feature flags or browser settings can be sized with 2^n or C(n, k) before deciding to run them.
  • Probability displays in dashboards and games, such as the chance of a certain hand of cards, are counts from these formulas divided by the total count.

Related algorithms