22. Generate Parentheses
Medium LeetCodeGiven 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
How to solve the problem
- Backtracking (DFS)
python
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
m = n * 2 # Total length of the result string
result = []
path = [''] * m # Temporary path for current parenthesis sequence
# i: current position in path
# open: number of '(' used so far
def dfs(i, open):
# If we've used up all positions, add to result
if i == m:
result.append(''.join(path))
return
# If we can still add '(', do so
if open < n:
path[i] = '('
dfs(i + 1, open + 1)
# If number of ')' used so far < number of '(' used, we can add ')'
if i - open < open:
path[i] = ')'
dfs(i + 1, open)
dfs(0, 0)
return result
Complexity
- Time complexity: O(K*C(n, k))
- Space complexity: O(K*C(n, k))
Comments
No comments yet. Be the first to comment!