Introduction

The number of valid ways to arrange n pairs of parentheses is given by the nth Catalan number. A valid arrangement is one where every closing parenthesis matches an earlier opening parenthesis and no prefix of the string ever contains more closings than openings.

Recognize the Catalan Pattern

This is not a plain permutation problem. If you have n opening symbols and n closing symbols, there are many ways to shuffle them, but most of those strings are invalid because they close before they open.

For example, with n = 3, these are valid:

• '((()))'
• '(()())'
• '(())()'
• '()(())'
• '()()()'

That gives a total of 5, which is the third Catalan number. The closed form is:

C(n) = binomial(2n, n) / (n + 1)

The first few values are:

• 'C(0) = 1'
• 'C(1) = 1'
• 'C(2) = 2'
• 'C(3) = 5'
• 'C(4) = 14'

Once you recognize that the question is really about Catalan numbers, the counting problem becomes much easier to classify.

Count with Dynamic Programming

A practical way to compute the count is to use the Catalan recurrence:

C(n) = sum(C(i) * C(n - 1 - i)) for each i from 0 to n - 1

This recurrence has a useful interpretation. Pick one pair of outer parentheses. Everything inside that pair contributes one Catalan subproblem, and everything to the right contributes another.

1def count_parenthesis(n: int) -> int:
2    dp = [0] * (n + 1)
3    dp[0] = 1
4
5    for pairs in range(1, n + 1):
6        total = 0
7        for left_size in range(pairs):
8            right_size = pairs - 1 - left_size
9            total += dp[left_size] * dp[right_size]
10        dp[pairs] = total
11
12    return dp[n]
13
14
15for n in range(6):
16    print(n, count_parenthesis(n))

This runs in O(n^2) time and O(n) space, which is usually fine for interview-style inputs and small combinatorics tasks.

Generate the Actual Valid Strings

Sometimes the question asks for the arrangements themselves, not just the count. In that case, backtracking is the cleanest approach.

1def generate_parenthesis(n: int):
2    result = []
3
4    def backtrack(current: str, open_count: int, close_count: int):
5        if len(current) == 2 * n:
6            result.append(current)
7            return
8
9        if open_count < n:
10            backtrack(current + "(", open_count + 1, close_count)
11
12        if close_count < open_count:
13            backtrack(current + ")", open_count, close_count + 1)
14
15    backtrack("", 0, 0)
16    return result
17
18
19print(generate_parenthesis(3))

The key rule is the second branch: you may append ) only when there is already an unmatched ( available. That local rule enforces the global validity condition automatically.

Why Prefix Validity Matters

Many incorrect solutions check only the final counts and ignore the prefixes. But a string such as ())(() has three openings and three closings and is still invalid because one prefix closes too early.

That prefix constraint is the whole structure of the problem. It is also why the same count appears in other Catalan-number settings:

• binary tree shapes
• valid stack permutations
• polygon triangulations
• certain grid paths that never cross a boundary

Seeing those connections helps you recognize the same pattern when it appears in a different disguise.

Use the Formula for Large Counts

If you only need the number and not the actual strings, the closed-form formula can be faster and simpler than building a dynamic-programming table.

1import math
2
3
4def catalan(n: int) -> int:
5    return math.comb(2 * n, n) // (n + 1)
6
7
8print(catalan(4))
9print(catalan(10))

This is a good choice when the question is purely combinatorial and the language provides a reliable binomial function.

Common Pitfalls

• Counting all permutations of n openings and n closings instead of only the balanced ones.
• Checking only final totals and forgetting the prefix validity rule.
• Using naive recursion for counting without memoization or dynamic programming.
• Confusing the counting problem with the generation problem. They are related, but the algorithms are different.
• Assuming this problem is unique instead of recognizing it as a Catalan-number pattern.

Summary

• The number of valid arrangements of n parenthesis pairs is the nth Catalan number.
• The defining rule is that no prefix may contain more closings than openings.
• Use dynamic programming when you want a constructive counting method.
• Use backtracking when you need the actual valid strings.
• Use the closed-form Catalan formula when you only need the count.