22. Generate Parentheses - LeetCode

Problem Description

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: ["()"]

My Idea

The idea here is that as seen in 20. Valid Parentheses for the parentheses to be well-formed, we need the number of opening ones to match the number of closing ones. Since there are different possible combinations for the parentheses, we use recursion and backtracking. A global stack is used to hold the current possible sequence for each branch.

My solution

# Time Complexity: O(2^n)
def generateParenthesis(n: int) -> list[str]:
    stack = []
    res=[]
    def backtrack(openN,closedN):
        if openN==closedN==n:
            res.append("".join(stack))
            return
        if openN < n:
            stack.append("(")
            backtrack(openN+1,closedN)
            stack.pop()
        if openN>closedN:
            stack.append(")")
            backtrack(openN,closedN+1)
            stack.pop()
    backtrack(0,0)
    return res