Generate Parentheses LeetCode Problem 22 [Python Solution]

Generate Parentheses LeetCode Problem 22 is about generating all combinations of well-formed parentheses given n pairs of parentheses.

We will walk you through the problem, provide a step-by-step explanation of the solution, and discuss time and space complexity.

Question: Generate Parentheses LeetCode Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Problem Overview

The problem statement is quite simple.

Given an integer n, we need to generate all possible combinations of well-formed parentheses with n pairs.

Well-formed parentheses are those in which every opening parenthesis has a corresponding closing parenthesis and they are properly nested.

Example

For example:

If n = 3, the valid combinations are: ["((()))", "(()())", "(())()", "()(())", "()()()"]
If n = 1, the only valid combination is: ["()"]

Understanding the Constraints

Before we dive into the solution, let’s understand the constraints implicit in the problem statement:

We need to generate all possible combinations, which means there could be many valid solutions.
The number of pairs, n, can vary. So, we need a flexible solution that can handle different values of n.

Now that we have a clear understanding of the problem, let’s proceed with the solution.

Bruteforce Approach

One way to tackle this problem is to use a recursive approach.

We can start with an empty string and keep adding parentheses to it, ensuring that we maintain the rules of well-formed parentheses.

There are two rules we must follow:

We can add an opening parenthesis if the count of opening parentheses is less than n.
We can add a closing parenthesis if the count of closing parentheses is less than the count of opening parentheses.

Let’s walk through the solution step by step with an example:

Suppose n = 3, and we start with an empty string. Initially, we have 0 opening and 0 closing parentheses.

We can add an opening parenthesis because the count of opening parentheses (0) is less than n. Our string becomes "(".
Now, we have 1 opening and 0 closing parentheses. We can either add an opening or a closing parenthesis. We chose to add an opening parenthesis. Our string becomes "((".
We continue this process, making choices based on the rules until we reach a valid combination.

Here’s a visual representation of the process:

"(" (1 open, 0 close)
"(((" (2 open, 0 close)
"(()" (2 open, 1 close)
"())" (2 open, 2 close)
"(())" (3 open, 2 close)
"()" (3 open, 3 close)

We’ve generated one valid combination.

To find all combinations, we backtrack and explore other choices at each step.

Efficient Solution

The brute-force approach we discussed earlier works, but it can be optimized.

Instead of constructing the combinations as strings, we can use a stack to keep track of the current state.

Here’s a Python solution that follows this optimized approach:

Generate Parentheses LeetCode Problem Solution in Python

This Python code uses a stack to build valid combinations efficiently.

View on GitHub ➹

def generateParenthesis(self, n: int) -> List[str]:
    stack = []
    res = []

    def backtrack(openN, closedN):
        if openN == closedN == n:
            res.append("".join(stack))
            return

        if openN &lt; n:
            stack.append("(")
            backtrack(openN + 1, closedN)
            stack.pop()
        if closedN &lt; openN:
            stack.append(")")
            backtrack(openN, closedN + 1)
            stack.pop()

    backtrack(0, 0)
    return res

The backtrack function recursively explores all possible combinations, following the rules we discussed earlier.

Time and Space Complexity

Let’s analyze the time and space complexity of our efficient solution:

Time Complexity: The time complexity of this solution isO(2^n) because, in the worst case, we generate all possible combinations of parentheses.
Space Complexity: The space complexity is O(n) as we use a stack to keep track of the current state, and the depth of recursion is at most n.

Reasoning Behind Our Efficient Approach

Our efficient approach uses backtracking to construct valid combinations of parentheses.

The key idea is to maintain the counts of open and closed parentheses and make choices based on those counts while ensuring we stay within the constraints.

Here’s a breakdown of our efficient approach:

We start with an empty stack to represent our current combination and an empty list res to store valid combinations.
The backtrack function takes two arguments: openN and closedN, which represent the counts of open and closed parentheses, respectively.
We check if openN and closedN are both equal to n, which means we have a valid combination. We join the characters in the stack and append the resulting string to our res list.
We make two choices:

If openN is less than n, we can add an opening parenthesis to the stack. We increment openN, call backtrack recursively, and then remove the added parenthesis from the stack (backtrack).
If closedN is less than openN, we can add a closing parenthesis to the stack. We increment closedN, call backtrack recursively, and then remove the added parenthesis from the stack (backtrack).

We start the backtracking process by calling backtrack(0, 0) with both counts initialized to 0.

This approach systematically explores all valid combinations while avoiding invalid ones efficiently.

Conclusion

In this blog post, we’ve minified the LeetCode problem 22, Generate Parentheses, where we needed to generate all combinations of well-formed parentheses.

We’ve explained the problem, provided a step-by-step walkthrough of the efficient solution using backtracking, and analyzed the time and space complexity.

This problem is an excellent example of using recursion and backtracking to generate valid combinations.

We hope this explanation has been helpful in understanding the solution.

If you have any questions, suggestions, or comments, please feel free to share them below.

Happy coding!