Number of Valid Parentheses – Catalan Number Pattern

Problem Statement

You are given an integer n representing the length of a parentheses string. Your task is to count how many valid parentheses expressions of length n can be formed using only '(' and ')'.

A valid parentheses expression must satisfy two conditions:

Every opening bracket must have a corresponding closing bracket.
Brackets must close in the correct order.

Examples

()()    → Valid
(())    → Valid
)()(    → Invalid
))((    → Invalid

Example 1

Input

n = 2

Output

Valid Expression

()

Example 2

Input

n = 4

Output

Valid Expressions

(())
()()

Example 3

Input

n = 6

Output

Understanding the Problem

At first glance, this appears to be a string-generation problem.

A straightforward idea would be:

Generate all possible combinations of '(' and ')'.
Check which strings are valid.
Count the valid ones.

However, the number of possible strings grows exponentially, making this approach inefficient for larger values of n.

The key is to discover the mathematical pattern hidden behind balanced parentheses sequences.

Important Observation

A valid parentheses string always contains:

Equal number of '(' and ')'

Therefore:

n must be even

If n is odd, it is impossible to form a valid expression.

Example

n = 3

No matter how the brackets are arranged, one bracket will remain unmatched.

Therefore:

Answer = 0

Discovering the Pattern

Let's count valid expressions for small lengths.

Length = 0

Count:

The empty string is considered valid.

Length = 2

Count:

Valid expression:

()

Length = 4

Count:

Valid expressions:

(())
()()

Length = 6

Count:

Valid expressions:

((()))
(()())
(())()
()(())
()()()

The sequence becomes:

1, 1, 2, 5, 14, 42, ...

This famous sequence is known as the Catalan Numbers.

What Are Catalan Numbers?

Catalan Numbers appear in many counting problems involving recursive structures.

The nth Catalan Number is represented as:

C(n)

and is given by:

C_n=\frac{1}{n+1}\binom{2n}{n}

where:

C(2n, n)

is the binomial coefficient.

For valid parentheses:

Length = 2m
Answer = Catalan(m)

Why Catalan Numbers Work

Every valid parentheses expression starts with an opening bracket.

That opening bracket must match with some closing bracket later in the string.

This naturally divides the expression into smaller valid expressions.

Example

(()())

can be viewed as:

( valid ) valid

This recursive structure is exactly what Catalan Numbers count.

Instead of generating all possible expressions, we directly compute the corresponding Catalan Number.

Dry Run

Consider:

n = 6

Since:

n = 2m

we have:

m = 3

We need:

Catalan(3)

Using the formula:

Catalan(3)=\frac{\binom{6}{3}}{4}

Calculate:

C(6,3) = 20

Therefore:

Catalan(3) = 20 / 4 = 5

Answer:

Optimized Approach

Step 1

Check whether n is odd.

If:

n % 2 != 0

return:

Step 2

Compute:

m = n / 2

Step 3

Calculate:

C(2m, m)

Step 4

Divide by:

m + 1

to obtain the Catalan Number.

C++ Solution

class Solution {
public:
    int findWays(int n) {

        if (n % 2)
            return 0;

        int m = n / 2;

        long long catalan = 1;

        for (int i = 0; i < m; i++) {
            catalan = catalan * (2 * m - i) / (i + 1);
        }

        catalan /= (m + 1);

        return (int)catalan;
    }
};

Why This Works

The formula:

Catalan(m)=\frac{\binom{2m}{m}}{m+1}

directly counts the number of balanced parentheses sequences containing m pairs of brackets.

Since every valid expression corresponds to exactly one balanced sequence, the formula gives the answer without generating any strings.

Complexity Analysis

Time Complexity

O(n)

We compute the binomial coefficient using a single loop.

Space Complexity

O(1)

Only a few variables are used.

Pattern Recognition for Interviews

Whenever you encounter problems involving:

Valid Parentheses Counting
Balanced Bracket Sequences
Number of Binary Search Trees
Mountain Ranges
Non-Crossing Handshakes
Polygon Triangulation

think of:

Catalan Numbers

These problems often share the same recursive structure and counting logic.

Common Catalan Number Sequence

The first few Catalan Numbers are:

n :  0  1  2  3   4   5    6
C :  1  1  2  5  14  42  132

These values appear repeatedly in many combinatorial counting problems.

Key Takeaway

The most important observation is that a valid parentheses string of length n must contain exactly n/2 pairs of brackets.

The number of such valid arrangements is not computed through simulation or backtracking. Instead, it is given directly by the Catalan Number:

Catalan(m)=\frac{\binom{2m}{m}}{m+1}

where:

m = n / 2

Recognizing the Catalan pattern transforms what appears to be an exponential counting problem into a simple mathematical solution.

Summary

To count valid parentheses expressions of length n, first verify that n is even. A valid expression requires exactly n/2 opening and n/2 closing brackets arranged in a balanced manner. The number of such expressions is given by the Catalan Number corresponding to m = n/2. Using the Catalan formula allows the answer to be computed efficiently in O(n) time and O(1) space without generating any parentheses strings.