22_Generate Parentheses

[Medium][String, Backtracking]

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

Example:

Input: n = 3

Output:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

Idea:

• Generate parentheses one by one. At each position, there are 3 possibilities:

  1. Add "(": if there are "(" remains to be added.

  2. Add ")": If the number of ")" is less than the number of "(" in the prefix.

• Write recursion at each position for the two possibilities.

Time Complexity: $O(\frac{(2n)!}{n! (n+1)!})$ from EPI page 235. Don't know how to compute.

Space Complexity: only need space for the output

def generateParenthesis(n):
    """
    :type n: int
    :rtype: List[str]
    """        
    def helper(left, right, prefix):
        # left is the number of "(" remains to be added
        # right is the number of ")" remains to be added
        # prefix is the parentheses already added

        if right == 0:
            output.append(prefix)
            return

        # case when we are able to insert "("
        if left > 0:
            helper(left-1, right, prefix + "(")

        # case when we are able to insert ")"
        if right > left:
            helper(left, right - 1, prefix + ")")


    output = []
    helper(n, n, "")
    return output