class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(s: str, open_count: int, close_count: int) -> None:
            # If the current string is of the correct length, add it to the results
            if len(s) == 2 * n:
                results.append(s)
                return

            # If we can add an opening parenthesis, do so and recurse
            if open_count < n:
                backtrack(s + "(", open_count + 1, close_count)

            # If we can add a closing parenthesis, do so and recurse
            if close_count < open_count:
                backtrack(s + ")", open_count, close_count + 1)

        results = []
        backtrack("", 0, 0)
        return results