LeetCode 22: Generate Parentheses

Problem Restatement

We are given an integer n.

We need to generate all combinations of well-formed parentheses using exactly n pairs.

For example, if:

n = 3

then every result must contain:

3 opening parentheses
3 closing parentheses

and the parentheses must be valid.

The problem asks for all valid strings, not just the number of valid strings. The constraint is 1 <= n <= 8.

Input and Output

Example function shape:

def generateParenthesis(n: int) -> list[str]:
    ...

Examples

Example 1:

n = 3

Output:

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

Example 2:

n = 1

Output:

["()"]

First Thought: Generate Every String

One possible approach is to generate every string of length 2n made of ( and ).

For n = 3, every candidate has length 6.

Each position has two choices:

(
)

So there are:

2^(2n)

candidate strings.

After generating each string, we check whether it is valid.

This works, but it wastes work because most strings are invalid.

For example:

")))((("

can never become valid. We should avoid generating invalid prefixes.

Key Insight

Build the string from left to right.

At any point, we only need two counts:

We can add ( if:

open_count < n

We can add ) if:

close_count < open_count

The second rule is important.

It prevents invalid prefixes like:

")"
"())"

A closing parenthesis is only valid if there is an unmatched opening parenthesis before it.

Backtracking Tree

For:

n = 2

Start with an empty path.

We can add (:

(

From there, we can add another (:

((

Now we cannot add more ( because open_count == n.

We must add ):

(()

Then add the final ):

(())

Backtrack and try another branch:

()

Then add (:

()(

Then add ):

()()

So the answer for n = 2 is:

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

Algorithm

1. Create an empty result list.
2. Create an empty path list.
3. Define a backtracking function with:
   • open_count
   • close_count
4. If the path length is 2 * n, add the path as a string.
5. If open_count < n, add ( and recurse.
6. If close_count < open_count, add ) and recurse.
7. Return the result list.

Correctness

The algorithm only adds ( when fewer than n opening parentheses have been used. So no generated string can contain more than n opening parentheses.

The algorithm only adds ) when close_count < open_count. So at every prefix, the number of closing parentheses never exceeds the number of opening parentheses.

These two rules are exactly the conditions needed for a parentheses string to remain valid while being built left to right.

When the path length reaches 2 * n, the string has exactly n opening parentheses and exactly n closing parentheses. Since every prefix has stayed valid, the completed string is well-formed.

The algorithm tries every legal choice at every step, so every well-formed parentheses string is eventually generated.

Therefore the algorithm returns exactly all valid combinations.

Complexity

C_n is the nth Catalan number, the number of valid parentheses strings with n pairs.

The recursion path uses O(n) extra space.

Implementation

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

        def backtrack(open_count: int, close_count: int) -> None:
            if len(path) == 2 * n:
                result.append("".join(path))
                return

            if open_count < n:
                path.append("(")
                backtrack(open_count + 1, close_count)
                path.pop()

            if close_count < open_count:
                path.append(")")
                backtrack(open_count, close_count + 1)
                path.pop()

        backtrack(0, 0)

        return result

Code Explanation

The result list stores complete valid strings:

result = []

The path stores the current partial string:

path = []

The helper function receives the number of opening and closing parentheses already used:

def backtrack(open_count: int, close_count: int) -> None:

When the path reaches length 2 * n, it is complete:

if len(path) == 2 * n:
    result.append("".join(path))
    return

Add an opening parenthesis only if we still have one available:

if open_count < n:
    path.append("(")
    backtrack(open_count + 1, close_count)
    path.pop()

Add a closing parenthesis only if it can close a previous opening parenthesis:

if close_count < open_count:
    path.append(")")
    backtrack(open_count, close_count + 1)
    path.pop()

Start from no parentheses used:

backtrack(0, 0)

Testing

def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(s.generateParenthesis(1)) == ["()"]

    assert normalize(s.generateParenthesis(2)) == [
        "(())",
        "()()",
    ]

    assert normalize(s.generateParenthesis(3)) == [
        "((()))",
        "(()())",
        "(())()",
        "()(())",
        "()()()",
    ]

    print("all tests passed")

run_tests()