How hard is LeetCode 22. Generate Parentheses?

LeetCode 22. Generate Parentheses is rated Medium on LeetCode.

What is the time complexity of LeetCode 22. Generate Parentheses?

The Python solution on this page runs in O(2^{n\times 2} \times n).

What is the space complexity of LeetCode 22. Generate Parentheses?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 22. Generate Parentheses cover?

LeetCode 22. Generate Parentheses is tagged String, Dynamic Programming and Backtracking on LeetCode.

Generate Parentheses — LeetCode 22 Python Solution

MediumStringDynamic ProgrammingBacktracking

Problem: #22
Pattern: Backtracking
Reading time: 2 min
Source: leetcode.com

The problem

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

Example

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

Python solution

Python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(l, r, t):
            if l > n or r > n or l < r:
                return
            if l == n and r == n:
                ans.append(t)
                return
            dfs(l + 1, r, t + '(')
            dfs(l, r + 1, t + ')')

        ans = []
        dfs(0, 0, '')
        return ans

Complexity

Measure	Complexity
Time	O(2^{n\times 2} \times n)
Space	O(n) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 22. Generate Parentheses is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

On study lists

This problem is on NeetCode 150 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 22. Generate Parentheses?: LeetCode 22. Generate Parentheses is rated Medium on LeetCode.
What is the time complexity of LeetCode 22. Generate Parentheses?: The Python solution on this page runs in O(2^{n\times 2} \times n).
What is the space complexity of LeetCode 22. Generate Parentheses?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 22. Generate Parentheses cover?: LeetCode 22. Generate Parentheses is tagged String, Dynamic Programming and Backtracking on LeetCode.