Basic Problemscountingcombinatorics

Count Valid Parenthesis

Given n pairs of parentheses, count how many distinct strings of balanced, well-formed parentheses can be built from them.

Do this lesson first: climbing stairs

Example input

n = 3

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = sum over k from 0 to i - 1 of dp[k] × dp[i - 1 - k]

Ask where the first opening bracket closes. Every non-empty balanced string starts with (, and that bracket has exactly one partner ). Between them sits a balanced string of some k pairs; after the partner sits a balanced string of the other i - 1 - k pairs. The inside and the outside are chosen independently, so for one k the counts multiply: dp[k] × dp[i - 1 - k]. Each string has one partner for its first bracket, so it falls under exactly one k, and the values of k are added. No split beats another; they are all added, not compared. The same loop over a split point returns in the interval family, where a split is chosen by min rather than summed.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1: zero pairs make exactly one balanced string, the empty one. It is what fills the inside of () and the space after the last pair. Set it to 0 and dp[1] = 0 × 0 = 0, and since every string bottoms out in an empty (), the whole row collapses to 0. Every cell reads only smaller pair counts, so filling left to right works.

i=0

i=1

i=2

i=3

i=4

1

2

5

14

count-valid-parenthesis.ts

1function countBalanced(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[0] = 1;
4 for (let pairs = 1; pairs <= n; pairs++) {
5 for (let inside = 0; inside < pairs; inside++) {
6 dp[pairs] += dp[inside] * dp[pairs - 1 - inside];
7 }
8 }
9 return dp[n];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

count-valid-parenthesis.ts

1function countBalanced(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[0] = 1;
4 for (let pairs = 1; pairs <= n; pairs++) {
5 for (let inside = 0; inside < pairs; inside++) {
6 dp[pairs] += dp[inside] * dp[pairs - 1 - inside];
7 }
8 }
9 return dp[n];
10}

Where people go wrong

Splitting a string wherever its prefix balances, instead of only at the partner of its first bracket. ()()() balances after 2, 4 and 6 characters, so pairing a balanced prefix with a balanced remainder at every such point counts it three times. Across the five strings with 3 pairs that rule finds 9 splits where the answer is 5. The first bracket's partner is unique, which is what gives every string exactly one split.

Allow two bracket types, ( ) and [ ], properly nested.
Each pair picks its type independently, so every term gains a factor of 2 for the first pair's type and the answer becomes dp[n] × 2ⁿ. The split at the first bracket's partner does not change.
Count only strings whose nesting depth never exceeds d.
The state gains a depth budget: the inside of the first pair is counted with budget d - 1, the part after it keeps d. The split itself does not change.
Count the balanced strings of length n rather than with n pairs.
An odd length has none, and an even length 2m is the answer for m pairs. The table is the same; only the index is halved.

Count Unique BSTs Ways to Triangulate a Polygon