Generate Parentheses

https://www.lintcode.com/problem/generate-parentheses

# Solution

Complexity (bounded by the n-th Catalan number 1n+1(2nn)4nn\frac{1}{n+1} \binom{2n}{n} \le \frac{4^n}{\sqrt{n}}):

  • time: O(4nn)O(\frac{4^n}{\sqrt{n}})
  • space: O(4nn)O(\frac{4^n}{\sqrt{n}}) due to implicit stack space
def generateParenthesis(self, n: int) -> List[str]:
    res = []

    def dfs(l, r, path):
        # exit when running out of left/right parentheses
        if l == 0 and r == 0:
            res.append(path)
            return
        # error if # of ')' more than # of '('
        if r < l:
            return
        # Use a left parenthesis
        if l > 0:
            dfs(l - 1, r, path + '(')
        # Use a right parenthesis
        if r > 0:
            dfs(l, r - 1, path + ')')

    dfs(n, n, '')
    return res
Last Updated: 7/19/2020, 3:45:14 PM