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:
Examples
()() → Valid
(()) → Valid
)()( → Invalid
))(( → Invalid
Example 1
Input
n = 2
Output
1
Valid Expression
()
Example 2
Input
n = 4
Output
2
Valid Expressions
(())
()()
Example 3
Input
n = 6
Output
5
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:
1
The empty string is considered valid.
Length = 2
Count:
1
Valid expression:
()
Length = 4
Count:
2
Valid expressions:
(())
()()
Length = 6
Count:
5
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:
5
Optimized Approach
Step 1
Check whether n is odd.
If:
n % 2 != 0
return:
0
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.