Day 11: Generate Parentheses - leetcode - Python3

 

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 8

SOLUTION:

class Solution:

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

        stack: List[str]=[]

        result: List[str]=[]

        def trackN(open: int,close: int):

            if open == close == n:

                result.append("".join(stack))

                return

               

           

            if open < n:

                stack.append("(")

                trackN(open +1, close)

                stack.pop()

            if close < open:

                stack.append(")")

                trackN(open, close +1)

                stack.pop()

        trackN(0,0)

        return result

Time Complexity:  O((4^n)/(n^(3/2)))

• • The number of valid combinations of parentheses is given by the n-th Catalan number.
  • The n-th Catalan number is approximately (4^n)/(n^(3/2)).
  • Therefore, the time complexity is O((4^n)/(n^(3/2))).

Space Complexity: The space complexity of the function is O(n). This is because the function uses a stack to store the parentheses that have been generated so far.

The trackN() function recursively calls itself to generate all possible combinations of parentheses. Each time the function is called, it adds a new parenthesis to the stack. When the function reaches a point where the number of open parentheses is equal to the number of closed parentheses, it adds the current combination of parentheses to the result list and then removes the last parenthesis from the stack. This ensures that the parentheses are added in the correct order.

Here is a breakdown of how the trackN() function works:

• If the number of open parentheses is equal to the number of closed parentheses, the function adds the current combination of parentheses to the result list and then returns.
• If the number of open parentheses is less than the number of closed parentheses, the function adds a new open parenthesis to the stack and then calls itself recursively.
• If the number of closed parentheses is less than the number of open parentheses, the function adds a new closed parenthesis to the stack and then calls itself recursively.

The stack.pop() method is used to remove the last parenthesis from the stack after each recursive call. This ensures that the parentheses are added in the correct order.