Quiz
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
- 1 <= n <= 8
Answer
Intuition
Start by building a string from "(", which is an open tag.
At each step:
if the number of used open tags is less than n, we can add an "(".
if the number of used close tags is less than n and less than the number of used open tags, we can add a ")".
Algorithm: divide the problem into smaller steps, each depending on the previous state, so we can use recursion to build the result.
1. initialize counters for used open and close tags.
2. if these counts are equal to `n`, we get a complete pattern.
3. else, we consume an open or close tag and go back to 2.
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
patterns = []
def dfs(current: list[str], open_used: int, close_used: int):
if open_used == n and close_used == n:
patterns.append("".join(current))
return
if open_used < n:
current.append("(")
dfs(current, open_used + 1, close_used)
current.pop()
if close_used < n and open_used > close_used:
current.append(")")
dfs(current, open_used, close_used + 1)
current.pop()
dfs([], 0, 0)
return patterns
To avoid creating a copy of current at every step (which takes O(N) time), we append and pop after processing.
This pop operation is needed to keep the correct current state.
If we don't use pop, the current state is shared across recursion states. (shared mutable object)
This algorithm needs a join for each pattern, so it takes O(N) per pattern. The number of valid patterns is the Catalan number, so the total time complexity is O(CatalanNumber * N).
The space complexity is O(N) for the current state.