LeetCode 22 - Generate Parentheses

The problem asks us to generate every possible valid combination of n pairs of parentheses. A valid parentheses string is one where every opening parenthesis ( has a matching closing parenthesis ), and the parentheses are properly nested.

leetcodemediumstringdynamic-programmingbacktracking

LeetCode Problem 22

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Backtracking

Solution

Problem Understanding

The problem asks us to generate every possible valid combination of n pairs of parentheses.

A valid parentheses string is one where every opening parenthesis ( has a matching closing parenthesis ), and the parentheses are properly nested. For example, "(()())" is valid because every opening bracket is closed in the correct order. However, strings like "(()" or ")(" are invalid because the parentheses are unbalanced or improperly ordered.

The input consists of a single integer n, which represents how many pairs of parentheses we must use. Since each pair contains two characters, every generated string will have length 2 * n.

The output should contain all unique well-formed parentheses combinations that can be formed using exactly n opening parentheses and n closing parentheses.

The constraints are relatively small:

1 <= n <= 8

Even though n is small, the number of valid combinations grows quickly. The count of valid combinations is given by the Catalan numbers. For example:

  • n = 1 produces 1 combination
  • n = 3 produces 5 combinations
  • n = 8 produces 1430 combinations

This means brute force generation becomes increasingly inefficient because most generated strings are invalid.

An important edge case is n = 1, where only one valid result exists: "()". Another subtle issue is ensuring we never place more closing parentheses than opening parentheses at any point during construction. A naive implementation might generate invalid prefixes such as ")(", which can never become valid later.

The problem guarantees that n is at least 1, so we do not need to handle empty input or negative values.

Approaches

Brute Force Approach

A straightforward idea is to generate every possible string of length 2 * n consisting of ( and ) characters. Since each position has two choices, there are 2^(2n) possible strings.

For every generated string, we can check whether it is valid using a balance counter:

  • Increment the counter for (
  • Decrement the counter for )
  • If the counter ever becomes negative, the string is invalid
  • At the end, the counter must be zero

This approach is correct because it examines every possible candidate and filters out the invalid ones.

However, it is extremely inefficient because the overwhelming majority of generated strings are invalid. For example, when n = 8, we would generate 2^16 = 65536 strings even though only 1430 are valid.

Optimal Backtracking Approach

The key insight is that we should never build invalid partial strings in the first place.

Instead of generating all possible combinations and filtering afterward, we can construct only valid prefixes recursively.

At any point during construction:

  • We can add ( if we still have opening parentheses remaining
  • We can add ) only if the number of closing parentheses used is less than the number of opening parentheses used

This guarantees that every partial string remains potentially valid.

This is a classic backtracking problem because:

  • We build the solution incrementally
  • We explore multiple choices recursively
  • We abandon invalid paths immediately

By pruning invalid branches early, we avoid unnecessary work and generate only valid combinations.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(2n) * n) O(2^(2n) * n) Generates every possible string and validates each one
Optimal O(Cn * n) O(n) excluding output Backtracking generates only valid combinations, where Cn is the nth Catalan number

Algorithm Walkthrough

  1. Start with an empty string and two counters:
  • open_count, the number of opening parentheses used
  • close_count, the number of closing parentheses used

These counters help us track whether the current partial string can still become valid. 2. If the current string length reaches 2 * n, we have used all parentheses.

At this point, the string must be valid because our construction rules never allow invalid states. We add it to the result list. 3. If open_count < n, we can safely add another opening parenthesis.

We recursively continue building the string with:

  • one more (
  • open_count + 1
  1. If close_count < open_count, we can add a closing parenthesis.

This condition is critical. It guarantees that we never create a prefix with more closing parentheses than opening ones, which would immediately make the string invalid. 5. Continue recursively exploring both possibilities until all valid strings are generated. 6. Backtracking naturally occurs when recursive calls return.

Each recursive branch explores one possible choice independently.

Why it works

The algorithm maintains an important invariant:

  • At every step, the partial string is valid or can still become valid.

The condition close_count <= open_count ensures we never create invalid prefixes. Since we only stop when the string reaches length 2 * n, every generated string contains exactly n opening and n closing parentheses in valid order.

Because every valid combination can be constructed using these rules, and invalid prefixes are never explored, the algorithm generates all valid solutions exactly once.

Python Solution

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

        def backtrack(current: str, open_count: int, close_count: int) -> None:
            # Base case: complete valid combination
            if len(current) == 2 * n:
                result.append(current)
                return

            # Add opening parenthesis if available
            if open_count < n:
                backtrack(current + "(", open_count + 1, close_count)

            # Add closing parenthesis if valid
            if close_count < open_count:
                backtrack(current + ")", open_count, close_count + 1)

        backtrack("", 0, 0)

        return result

The implementation uses a nested helper function called backtrack to recursively build valid parentheses strings.

The result list stores all valid combinations.

The recursive function accepts three parameters:

  • current, the current partially constructed string
  • open_count, how many opening parentheses have been used
  • close_count, how many closing parentheses have been used

The base case occurs when the string length reaches 2 * n. At that point, the string is complete and valid, so it is added to the result list.

The first recursive branch adds an opening parenthesis if we still have openings remaining.

The second recursive branch adds a closing parenthesis only when doing so keeps the string valid. The condition close_count < open_count prevents invalid prefixes such as ")(".

Because strings in Python are immutable, current + "(" creates a new string for each recursive call. This keeps recursive branches independent and avoids manual backtracking cleanup.

Finally, the recursion begins with an empty string and zero parentheses used.

Go Solution

func generateParenthesis(n int) []string {
    result := []string{}

    var backtrack func(current string, openCount int, closeCount int)

    backtrack = func(current string, openCount int, closeCount int) {
        // Base case
        if len(current) == 2*n {
            result = append(result, current)
            return
        }

        // Add opening parenthesis
        if openCount < n {
            backtrack(current+"(", openCount+1, closeCount)
        }

        // Add closing parenthesis
        if closeCount < openCount {
            backtrack(current+")", openCount, closeCount+1)
        }
    }

    backtrack("", 0, 0)

    return result
}

The Go implementation follows the same recursive backtracking strategy as the Python version.

One notable difference is that Go requires explicit declaration of the recursive function variable before assigning the function body. This is why the code first declares:

var backtrack func(current string, openCount int, closeCount int)

and then assigns the implementation afterward.

The result slice is initialized as an empty slice rather than nil, although both would work correctly here.

Strings in Go are immutable, similar to Python, so concatenating "(" or ")" creates new strings for recursive calls.

Integer overflow is not a concern because n <= 8, making all values extremely small.

Worked Examples

Example 1

Input:

n = 3

Expected output:

["((()))","(()())","(())()","()(())","()()()"]

The recursion explores states as follows:

Current String Open Count Close Count Action
"" 0 0 Add (
"(" 1 0 Add (
"((" 2 0 Add (
"(((" 3 0 Add )
"((()" 3 1 Add )
"((())" 3 2 Add )
"((()))" 3 3 Add to result

The algorithm then backtracks and explores alternative valid paths:

Current String Open Count Close Count Next Choice
"((" 2 0 Add )
"(()" 2 1 Add (
"(()(" 3 1 Continue
"(()())" 3 3 Add to result

Eventually all valid combinations are generated.

Example 2

Input:

n = 1

Expected output:

["()"]

Execution trace:

Current String Open Count Close Count Action
"" 0 0 Add (
"(" 1 0 Add )
"()" 1 1 Add to result

No other valid branches exist.

Complexity Analysis

Measure Complexity Explanation
Time O(Cn * n) Generates all valid combinations, each of length 2n
Space O(n) excluding output Recursive call stack depth is at most 2n

The number of valid parentheses combinations is the nth Catalan number:

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

This grows approximately as:

$C_n \approx \frac{4^n}{n^{3/2}\sqrt{\pi}}$

Since each valid string has length 2n, the total work becomes O(Cn * n).

The recursion depth never exceeds 2n, so auxiliary space usage is linear in n, excluding the output list itself.

Test Cases

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

        def backtrack(current: str, open_count: int, close_count: int):
            if len(current) == 2 * n:
                result.append(current)
                return

            if open_count < n:
                backtrack(current + "(", open_count + 1, close_count)

            if close_count < open_count:
                backtrack(current + ")", open_count, close_count + 1)

        backtrack("", 0, 0)

        return result

solution = Solution()

# Provided example for n = 1
assert solution.generateParenthesis(1) == ["()"]

# Provided example for n = 3
assert sorted(solution.generateParenthesis(3)) == sorted([
    "((()))",
    "(()())",
    "(())()",
    "()(())",
    "()()()"
])

# Smallest valid input
assert len(solution.generateParenthesis(1)) == 1

# Verify count for n = 2
assert sorted(solution.generateParenthesis(2)) == sorted([
    "(())",
    "()()"
])

# Verify Catalan count for n = 4
assert len(solution.generateParenthesis(4)) == 14

# Ensure all generated strings are unique
result = solution.generateParenthesis(4)
assert len(result) == len(set(result))

# Ensure all strings have correct length
result = solution.generateParenthesis(5)
assert all(len(s) == 10 for s in result)

# Ensure all generated strings are balanced
def is_valid(parentheses: str) -> bool:
    balance = 0

    for char in parentheses:
        if char == "(":
            balance += 1
        else:
            balance -= 1

        if balance < 0:
            return False

    return balance == 0

result = solution.generateParenthesis(5)
assert all(is_valid(s) for s in result)

# Stress test near upper constraint
assert len(solution.generateParenthesis(8)) == 1430
Test Why
n = 1 Validates smallest possible input
n = 3 Confirms standard example output
n = 2 Checks branching behavior
n = 4 count check Verifies Catalan number generation
uniqueness test Ensures no duplicate combinations
length validation Ensures every string uses exactly 2n characters
balance validation Confirms all outputs are well-formed
n = 8 stress test Verifies correctness near upper constraint

Edge Cases

One important edge case is the minimum input value, n = 1. In this situation, only a single valid combination exists: "()". Recursive solutions sometimes fail here because they incorrectly assume multiple branching possibilities. This implementation handles it naturally because once one opening parenthesis is added, the only valid next move is a closing parenthesis.

Another critical edge case involves invalid prefixes. For example, strings beginning with ")" can never become valid later. A naive brute force solution would still generate and test these strings. The backtracking solution avoids this entirely using the condition:

if close_count < open_count:

This guarantees that the number of closing parentheses never exceeds the number of opening parentheses during construction.

A third important edge case occurs near the upper constraint, n = 8. Although the input size appears small, the number of valid combinations grows quickly to 1430. Inefficient implementations that repeatedly validate strings or copy large structures unnecessarily may become slow. The recursive pruning strategy keeps the search space manageable by exploring only valid states.

A subtle implementation concern is ensuring every generated string uses exactly n opening and n closing parentheses. Some incorrect solutions stop recursion too early or allow extra openings. This implementation prevents that by:

  • allowing at most n opening parentheses
  • stopping only when the string length reaches 2 * n

This guarantees all outputs are complete and correctly balanced.