Core Insight Keep only items whose matching decision has not been made yet.
Common Pitfall Check that the stack is non-empty before reading its top.
Description
Generate all combinations of well-formed parentheses.
Constraints
- Time Complexity:
O(4^n/√n) - Space Complexity:
O(n)
Tags
stringdynamic-programmingbacktracking
Implementation Plan Translate the invariant into these small, testable moves.
- Read one item at a time.
- Push unresolved work.
- Match or remove work when its partner arrives.
- Validate the final stack state.
def generateParenthesis(n):
stack = []
res = []
def backtrack(openN, closedN):
if openN == closedN == n:
res.append("".join(stack))
return
if openN < n:
stack.append("(")
backtrack(openN + 1, closedN)
stack.pop()
if closedN < openN:
stack.append(")")
backtrack(openN, closedN + 1)
stack.pop()
backtrack(0, 0)
return res