Introduction

Generating all valid combinations of n pairs of parentheses is a classic backtracking problem. The key to its complexity is that the output size is already exponential, so no algorithm can be “truly fast” once n grows. The right complexity discussion is therefore about how close the algorithm gets to the size of the required output.

The Number of Valid Results Is the Catalan Number

The count of valid strings with n pairs of parentheses is the nth Catalan number. That count is C_n = (1 / (n + 1)) * binomial(2n, n).

For small values:

• 'n = 1 gives 1 result,'
• 'n = 2 gives 2 results,'
• 'n = 3 gives 5 results,'
• 'n = 4 gives 14 results.'

This matters because any algorithm that must output all valid strings has to spend at least enough time to emit those strings. So the lower bound is already proportional to the total output size.

Backtracking Generates Only Valid Prefixes

The standard algorithm uses backtracking. At each step you may add an opening parenthesis if you still have one available, and you may add a closing parenthesis only if it does not make the prefix invalid.

1def generate_parentheses(n):
2    result = []
3
4    def backtrack(current, opened, closed):
5        if len(current) == 2 * n:
6            result.append("".join(current))
7            return
8
9        if opened < n:
10            current.append("(")
11            backtrack(current, opened + 1, closed)
12            current.pop()
13
14        if closed < opened:
15            current.append(")")
16            backtrack(current, opened, closed + 1)
17            current.pop()
18
19    backtrack([], 0, 0)
20    return result
21
22print(generate_parentheses(3))

This algorithm is efficient in the right sense: it does not generate all 2^(2n) raw strings and then filter them. It generates only prefixes that can still become valid.

Time Complexity Is Theta(C_n * n)

There are C_n valid outputs, and each output has length 2n. Building or copying each finished string costs linear time in the output length, so the total running time is Theta(C_n * n).

Using the asymptotic growth of Catalan numbers, this becomes roughly Theta(4^n / sqrt(n)).

That is the useful answer for most interview and algorithm discussions. It acknowledges both facts:

• the result count is exponential,
• and the algorithm is essentially output-sensitive.

If someone says the complexity is just exponential, that is directionally true but incomplete. Theta(C_n * n) is more precise.

Why It Is Not O(4^n) in the Naive Sense

A naive generate-and-test approach would construct every string of length 2n from the alphabet of open and close parentheses. That produces 4^n candidates, most of which are invalid. Each candidate would then need validation, adding another linear factor.

The backtracking solution avoids that waste by pruning invalid prefixes immediately. That does not make the problem polynomial. It just means the algorithm scales with the number of valid answers rather than the number of all possible answers.

This distinction matters because it explains why backtracking is the right algorithmic pattern here.

Space Complexity Depends on What You Count

The recursion depth is O(n) because the construction path is at most 2n characters long. The working space for the current partial string is also O(n).

If you include the stored results, the total space becomes Theta(C_n * n) because you are keeping every generated string. In algorithm discussions, people often separate auxiliary space from result space for that reason.

A Small Example Helps Ground the Formula

For n = 3, the algorithm returns:

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

There are 5 outputs, each of length 6. Even if the control logic were free, you still have to write 30 characters to return the full answer. That is why output size is central to the complexity analysis.

Common Pitfalls

• Saying the algorithm is O(2^n) without accounting for the actual number of valid outputs.
• Saying the complexity is just the Catalan number and forgetting the linear cost to build each returned string.
• Confusing the efficient backtracking algorithm with brute-force generation of all length-2n strings.
• Ignoring the difference between auxiliary recursion space and full result-storage space.
• Treating exponential output problems as if they should have polynomial-time full enumeration algorithms.

Summary

• The number of valid parenthesis strings for n pairs is the Catalan number C_n.
• A good backtracking algorithm generates only valid prefixes.
• The total runtime to generate all answers is Theta(C_n * n).
• Asymptotically, that is about Theta(4^n / sqrt(n)).
• The algorithm is expensive because the output itself is exponentially large.