22. Generate Parentheses
## description
## 22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
1Input: n = 3
2Output: ["((()))","(()())","(())()","()(())","()()()"]Example 2:
1Input: n = 1
2Output: ["()"]- –1 <= n <= 8
Constraints:
## notes
### Intuition
Well-formed parentheses follow two rules: we can add an open bracket if we haven't used all n, and we can add a close bracket only if it wouldn't exceed the number of opens. Backtracking explores all valid combinations.
### Implementation
Use a recursive backtracking function tracking open count, closed count, and a stack for the current combination. Base case: when open == closed == n, we have a complete valid string—add it to results. Otherwise, if open < n, try adding an open bracket (recurse, then pop). If closed < open, try adding a close bracket (recurse, then pop).
### Edge-cases
No special edge cases. The constraints (open < n and closed < open) ensure only valid combinations are generated.
- –Time: O(4ⁿ/√n) — the n-th Catalan number represents valid combinations
- –Space: O(n) — recursion depth and stack for current combination
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def backtrack(self, open: int, closed: int, n: int, stack: List[str], result: List[str]):
5 if open == closed and closed == n:
6 result.append("".join(stack))
7 return
8
9 if open < n:
10 stack.append("(")
11 self.backtrack(open + 1, closed, n, stack, result)
12 stack.pop()
13
14 if closed < open:
15 stack.append(")")
16 self.backtrack(open, closed + 1, n, stack, result)
17 stack.pop()
18
19
20 def generateParenthesis(self, n: int) -> List[str]:
21 result = []
22 stack = []
23 self.backtrack(0, 0, n, stack, result)
24 return result
25
26
27
28
29if __name__ == "__main__":
30 # Include one-off tests here or debugging logic that can be run by running this file
31 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
32 solution = Solution()
33