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 = 1Output: ["()"]
Example 2:
Input: n = 3Output: ["((()))","(()())","(())()","()(())","()()()"]
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)