Generate Parentheses LeetCode solution in Python

1
class Solution:
2
    def generateParenthesis(self, n: int) -> list[str]:
3

4
        # Initialize the result
5
        res = []
6

7
        # Recursively go through all possible combinations
8
        def add(open, close, partialRes):
9

10
            nonlocal res
11

12
            # If we have added opening and closing parentheses n times, we reaches a solution
13
            if open == close == n:
14
                res.append("".join(partialRes))
15
                return
16

17
            # Add a closing parenthesis to the partial result if we have at least 1 opening parenthesis
18
            if close < open:
19
                add(open, close + 1, partialRes + [")"])
20

21
            # Add an opening parenthesis to the partial result if we haven't added n parenthesis yet
22
            if open < n:
23
                add(open + 1, close, partialRes + ["("])
24

25
        add(0, 0, [])
26

27
        return res