leetcode-22 Generate Parentheses

# Given n pairs of parentheses, write a function to generate all combinations
# of well-formed parentheses.
#
# Example 1:
# Input: n = 3
# Output: ["((()))","(()())","(())()","()(())","()()()"]
#
# Example 2:
# Input: n = 1
# Output: ["()"]
#
# Constraints:
# 1 <= n <= 8

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

        def backtrack(current, open_count, close_count):
            # Base case: generated n pairs
            if len(current) == 2 * n:
                result.append(current)
                return

            # Can add '(' if we haven't used all n opening brackets
            if open_count < n:
                backtrack(current + '(', open_count + 1, close_count)

            # Can add ')' if it won't exceed number of '('
            if close_count < open_count:
                backtrack(current + ')', open_count, close_count + 1)

        backtrack('', 0, 0)
        return result

    # Alternative: Using list for efficiency
    def generateParenthesis2(self, n: int) -> List[str]:
        result = []

        def backtrack(path, open_count, close_count):
            if len(path) == 2 * n:
                result.append(''.join(path))
                return

            if open_count < n:
                path.append('(')
                backtrack(path, open_count + 1, close_count)
                path.pop()  # backtrack

            if close_count < open_count:
                path.append(')')
                backtrack(path, open_count, close_count + 1)
                path.pop()  # backtrack

        backtrack([], 0, 0)
        return result

# Time Complexity: O(4^n / sqrt(n)) - Catalan number
# Space Complexity: O(n) - recursion depth
#
# Key Constraints:
# 1. open_count <= n: Can't use more than n opening brackets
# 2. close_count <= open_count: Can't have more closing than opening
#
# Why these constraints work?
# - Always add '(' when possible (open_count < n)
# - Only add ')' when it won't create invalid sequence (close_count < open_count)
# - This guarantees well-formed parentheses
#
# Decision Tree Example (n=2):
#                    ""
#                   /
#                  (
#                /   \
#              ((     ()
#             /        \
#           (()        ()(
#          /            \
#        (())          ()()
#
# Invalid paths are pruned by constraints!
#
# Related Problems:
# - Valid Parentheses (LC 20) - validation
# - Remove Invalid Parentheses (LC 301) - BFS/backtracking
# - Longest Valid Parentheses (LC 32) - DP
#
# AirBnB: Tests backtracking with constraint satisfaction