Generate Parentheses

View Generate Parentheses on LeetCode

Statistics

Time Complexity
O(2ⁿ) - The algorithm must explore each possible combination of strings of length 2n, resulting in 2²ⁿ time, but big-O ignores constant multiples, resulting in the O(2ⁿ) time complexity.

Space Complexity
O((2n)!/ (n! * (n + 1)!)) - The maximum space for all the strings can be represented by is represented by this formula.

Runtime Beats
74.89% of other submissions

Memory Beats
68.87% of other sumbissions

Explanation

The algorithm implements a recursive method backtrack and takes in three parameters: two integers representing the number of open and close parenthesis, and one string s. This method contains three conditional statements.

• if len(s) == n * 2: When executed, the string is at the maximum length and must be appended to the list, and this backtrack path must terminate.

• if open < n: To execute, there must be fewer open parentheses than the maximum amount n. When executed, a new branch of backtrack is created, exploring all possible paths with open + 1 open parenthesis.

• if close < open:To execute, there must be fewer close parentheses than open parentheses. When executed, a new branch of backtrack is created, exploring all possible paths with close + 1 close parenthesis.

Once the backtrack method is declared, create a list to contain all the output strings. After this, begin the backtracking algorithm with the input number of open and close parenthesis to 0 and the beginning string to an empty string.

Algorithm Used

Backtracking - An algorithmic technique that incrementally builds possible solutions by exploring all possible paths at each increment.

Visual Examples
Visualization of generate parentheses backtracking, click to view.

Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(open, close, s):
            if len(s) == n * 2:
                res.append(s)
                return 

            if open < n:
                backtrack(open + 1, close, s + '(')

            if close < open:
                backtrack(open, close + 1, s + ')')

        res = []
        backtrack(0, 0, '')
        return res