Generate Parentheses

Solution

Complexity is bounded by the n-th Catalan number $\frac{1}{n+1} \binom{2n}{n} \le \frac{4^n}{\sqrt{n}}$.

Complexity

time: $O(\frac{4^n}{\sqrt{n}})$
space: $O(\frac{4^n}{\sqrt{n}})$ (due to implicit stack space)

Backtracking

We only track the valid prefixes during the backtracking procedure.

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

    def backtrack(curr_str, left_count, right_count):
        if len(curr_str) == 2*n:
            res.append(curr_str)
            return
        if left_count < n: # a '(' can still be added
            backtrack(curr_str + '(', left_count+1, right_count)
        if left_count > right_count: # a ')' can be added to match a previous unmatched '('
            backtrack(curr_str + ')', left_count, right_count+1)
    
    backtrack('', 0, 0)
    return res

Closure Number (Divide and Conquer)

Consider the closure number of a valid parentheses sequence S: the least index >= 0 so that S[0], S[1], $\cdots$, S[2*index+1] is valid. Clearly, every parentheses sequence has a unique closure number. We can try to enumerate them individually.

Algorithm: For each closure number c, we know the starting and ending brackets must be at index 0 and 2*c + 1. Then, the 2*c elements between must be a valid sequence, plus the rest of the elements must be a valid sequence.

def generateParenthesis(self, n: int) -> List[str]:
    if n == 0: return ['']
    res = []
    for i in range(n):
        for left in self.generateParenthesis(i):
            for right in self.generateParenthesis(n-1-i):
                res.append('({}){}'.format(left, right))
    return res