Generate Parentheses
- 1 min read
- Stacks
- LC-Medium
- Backtracking
3 years ago
Solution
- We can only add a closing bracket if the current number of open brackets is greater than the current number of closing brackets
- This is a backtracking solution- at each step you either add an open bracket or a closing bracket
- You can only add an open bracket if the current number of open brackets is less than or equal to n
- You can only add a closing bracket if the current number of open brackets is more than the current number of closing brackets- i.e. something like (() - you can add a closing bracket.
- If the current string is (()), you cannot add another closing bracket.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def backtrack(open, closed, cur):
if open == closed == n:
ans.append(cur)
return
if open < n:
backtrack(open + 1, closed, cur + '(')
if open > closed:
backtrack(open, closed + 1, cur + ')')
backtrack(0, 0, '')
return ans