Problem Statement

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

Examples

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints

• 1 <= n <= 8

Intuition

In this problem, we're given an integer 'n' for this we need to generate well-formed parentheses.

Well-formed parentheses (or balanced parentheses) refer to a string where the opening and closing parentheses of different types match up correctly. Here's a breakdown:

• Types of parentheses: The most common types are round brackets "()", curly braces "{}", and square brackets "[]".

• Matching: Each opening parenthesis must have a corresponding closing parenthesis of the same type.

• Order: The closing parenthesis must appear after its corresponding opening parenthesis.

Examples of Well-formed Parentheses:

• (): A single pair of round brackets.

• (x + y) * z: Opening round bracket followed by an expression, then a closing round bracket. Another pair of round brackets multiplies the entire expression.

• { [a + b] * c }: Curly braces enclose an expression with square brackets inside. The square brackets are balanced within the curly braces.

Examples of Non-well-formed Parentheses:

• ( ): Missing opening parenthesis before the closing one.

• [ (x + y) ]: Mismatched parentheses. The opening bracket "[" doesn't have a corresponding closing bracket.

• { }: Empty curly braces. While technically no parentheses are unmatched, it's not a valid expression.

In this problem we have to generate formed well formed parentheses for '()'.

Using Include/Exclude

To solve this problem we can use backtracking and for each recursive call we can decide if we want to add '(' parentheses or ')' parentheses. This inclusion of '(' or ')' will work like this:

• If the number of opening parentheses is less than 'n', then this means we can still add a '(' parentheses to the current pattern.

• When we backtrack, if the number of closing parentheses is less than opening parentheses then we can add a ')' parentheses. So that we make balanced/well-formed parentheses.

• Also, for each recursive call, we keep checking if number of open and number of closed parentheses is equal to 'n' . Then we can add that pattern to the result array/list. This will be our base condition.

Code Solution

Python Code:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # initialize result array
        res=[]
        # call function to generate combination of valid parantheses pair
        self.generate(n,0,0,"",res)
        # return the result
        return res
    def generate(self,n,no_open,no_closed:int,curr_pattern:str,res:List[str]):
        # base case
        # if number of open and number of closed parantheses
        # is equal to 'n', then append the curr_pattern stirng to result array
        if no_open==n and no_closed==n:
            # append current pattern to result array
            res.append(curr_pattern)
            # return for this current recursive call
            return
        # if number of open parantheses is less than 'n'
        # it means that we can add another '(' to current pattern
        if no_open<n:
            # increase number of open parantheses
            # and add '(' to curr_pattern
            self.generate(n,no_open+1,no_closed,curr_pattern+'(',res)
        # if number of open parantheses is greater than number of closed parantheses
        # it means that we can add another ')' to current pattern
        if no_open>no_closed:
            # increase number of open parantheses
            # and add '(' to curr_pattern
            self.generate(n,no_open,no_closed+1,curr_pattern+')',res)

Time and Space complexity

Time Complexity:

$$O(2^n)$$

As for each recursive call we can make two other recursive calls.

Space Complexity:

$$O(n)$$

As this will be the maximum length of recursive call stack.

Recursive Tree

Here's the recursion tree for generateParenthesis(n=3):

                                 generate(3, 0, 0, "", [])
                                   /                     \
                                  /                       \
                             generate(3, 1, 0, (, [])        generate(3, 0, 1, "", []) (invalid)
                               /         \                      / \ (not explored)
                              /           \                    /   \ (not explored)
                         generate(3, 2, 0, ((), [])        generate(3, 1, 1, (), [])
                          /         \                      /         \
                         /           \                    /           \
                    generate(3, 3, 0, (((), [])        generate(3, 2, 1, (,()), [])
                     /         \                      /         \
                    /           \                    /           \
               (RESULT) generate(3, 3, 1, ((((), []))  generate(3, 3, 2, ((,()), [])
                                                             /         \ (not explored)
                                                            /           \ (not explored)
                                                       (RESULT) generate(3, 3, 3, (((,()), []))

Explanation:

1. The root node represents the initial call generate(3, 0, 0, "", []). Here n (number of parentheses) is 3, no_open (number of opening parentheses) is 0, no_closed (number of closing parentheses) is 0, curr_pattern (current string with parentheses) is empty, and res (result list) is empty.

2. Since no_open (0) is less than n (3), we explore the left branch. This branch adds a "(" to curr_pattern and increments no_open by 1, resulting in generate(3, 1, 0, (, []).

3. We continue down the left branch as no_open (1) is still less than n (3). This adds another "(" and increments no_open to 2, resulting in generate(3, 2, 0, (((), []).

4. Now, both no_open (2) and n (3) are equal, but no_closed (0) is still less than n. So, we explore the left branch again, adding a ")" and incrementing no_closed to 1, resulting in generate(3, 3, 1, ((((), [])).

5. Here, both no_open and no_closed are equal to n (3), satisfying the condition for a valid combination. The current pattern ((((), [])) is appended to the res list (marked as RESULT).

6. Backtracking: Since the left branch resulted in a valid combination, we don't explore further down that path. We backtrack to the previous node generate(3, 3, 0, (((), []).

7. However, the right branch at generate(3, 0, 1, "", []) is not explored because no_open (0) is less than or equal to no_closed (1). This is an invalid state as we cannot have more closing parentheses than opening parentheses at any point.

Following this process, the recursion tree explores all valid combinations of parentheses for n=3 and adds them to the res list.

Conclusion

As you can see 22. Generate Parentheses can be solved using recursion. In this problem we learn how at each recursive call we decide to add a '(' or ')' parentheses in the curr_pattern string.

I hope you got something useful from this blog post. If you've made it this far, please give it a like and drop your thoughts in the comments. Feel free to share any ideas for making future blog posts better.