---
title: "LeetCode #22: Generate Parentheses"
url: https://perrotta.dev/2025/12/leetcode-%2322-generate-parentheses/
last_updated: 2026-01-03
---


[LeetCode #22: Generate Parentheses](https://leetcode.com/problems/generate-parentheses):

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        def backtrack(n, o, s):
            assert n >= 0

            if n == 0:
                assert s
                ans.append(s + ')' * o)
                return

            # (
            backtrack(n - 1, o + 1, s + '(')

            # )
            if o > 0:
                backtrack(n, o - 1, s + ')')

        backtrack(n, 0, "")

        return ans
```

In each node, decide whether to add '(' or ')'.

`n` keeps track of available '('.

`o` keeps track of available ')'.

Strings in Python are immutable, making it easier to backtrack.

If we used an array, then we would have to employ a pattern like this:

```python
s.append('(')
backtrack(n - 1, o + 1, s)
s.pop()
```