👨‍💻 738LeetCode

Generate Parentheses

Question

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

Example

Given n = 3, solution = 
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

Every time can either add left paren or right paren.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def helper(curr, open, closed):
            if open == 0:  # Last case
                return [curr + ')' * closed]
            elif closed == 0:
                return helper(curr + '(', open - 1, closed + 1)
            return helper(curr + '(', open - 1, closed + 1) + \
                   helper(curr + ')', open, closed - 1)


        if n == 0:
            return []
        return helper('', n, 0)