Generate Parentheses

Problem Statement

You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

Example 1:

Input: n = 1
Output: ["()"]

Example 2:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

You may return the answer in any order.

Constraints:

• 1 <= n <= 7

You should aim for a solution as good or better than O(4^n / \sqrt{n}) time and O(n) space, where n is the number of parenthesis pairs in the string.

Recommended Time and Space Complexity

You should aim for a solution as good or better than O(4^n / \sqrt{n}) time and O(n) space, where n is the number of parenthesis pairs in the string.

Hint 1

A brute force solution would be to generate all possible strings of size 2n and add only the valid strings. This would be an O(n \cdot 2 ^ {2n}) solution. Can you think of a better way? Maybe you can use pruning to avoid generating invalid strings.

Hint 2

We can use backtracking with pruning. But what makes a string invalid? Can you think of a condition for this?

Hint 3

When the count of closing brackets exceeds the count of opening brackets, the string becomes invalid. Therefore, we can maintain two variables, open and close, to track the number of opening and closing brackets. We avoid exploring paths where close > open. Once the string length reaches 2n, we add it to the result.

Solution

Brute Force

def generate_parenthesis(n: int) -> List[str]:
    res = []

    def valid(s: str):
        open_count = 0
        for c in s:
            open_count += 1 if c == '(' else -1
            if open_count < 0:
                return False
        return not open_count

    def dfs(s: str):
        if n * 2 == len(s):
            if valid(s):
                res.append(s)
            return

        dfs(s + '(')
        dfs(s + ')')

    dfs("")
    return res

Time complexity: O(2 ^ {2n} \cdot n) Space complexity: O(2 ^ {2n} \cdot n)

Backtracking

def generate_parenthesis(n: int) -> List[str]:
    stack = []
    res = []

    def backtrack(open_n, closed_n):
        if open_n == closed_n == n:
            res.append("".join(stack))
            return

        if open_n < n:
            stack.append("(")
            backtrack(open_n + 1, closed_n)
            stack.pop()
        if closed_n < open_n:
            stack.append(")")
            backtrack(open_n, closed_n + 1)
            stack.pop()

    backtrack(0, 0)
    return res

Time complexity: O(\frac{4^n}{\sqrt{n}}) Space complexity: O(n)

Dynamic Programming

def generate_parenthesis(n):
    res = [[] for _ in range(n+1)]
    res[0] = [""]

    for k in range(n + 1):
        for i in range(k):
            for left in res[i]:
                for right in res[k-i-1]:
                    res[k].append("(" + left + ")" + right)

    return res[-1]

Time complexity: O(\frac{4^n}{\sqrt{n}}) Space complexity: O(n)