Generate Parentheses

Intuition

A prefix can still become a valid string as long as we have not used more opening brackets than allowed and we never close more than we have opened. By tracking the number of opening and closing brackets placed so far, we can decide at each step whether adding '(' or ')' is legal. Adding '(' is allowed whenever the count of opening brackets is still below n, and adding ')' is allowed only when there is an unmatched opening bracket. This prunes every dead branch before it starts.

Algorithm walkthrough

1. 1Start with an empty prefix and counters open = 0 and close = 0.
2. 2If the prefix length equals 2 * n, it is complete and balanced, so store a copy.
3. 3If open < n, append '(' and recurse with open increased by one.
4. 4If close < open, append ')' and recurse with close increased by one.
5. 5Undo the last character after each recursive call so sibling branches start from the same prefix.

Implementation

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []

        def backtrack(current: str, open_count: int, close_count: int) -> None:
            if len(current) == 2 * n:
                result.append(current)
                return
            if open_count < n:
                backtrack(current + "(", open_count + 1, close_count)
            if close_count < open_count:
                backtrack(current + ")", open_count, close_count + 1)

        backtrack("", 0, 0)
        return result