Solutions

# Backtracking. Basic rules: a) only add open par if open < n; b) only add close par if close < open.
# bactracking

# Backtracking with stack: O(4^n/sqrt(n)) time, O(n) space
def generate_parentheses(n: int) -> list[str]:
    stack = []
    res = []

    def backtrack(open_n: int, close_n: int):
        if open_n == close_n == n:
            res.append(''.join(stack))
            return
        
        if open_n < n:
            stack.append("(")
            backtrack(open_n + 1, close_n)
            stack.pop()

        if close_n < open_n:
            stack.append(")")
            backtrack(open_n, close_n + 1)
            stack.pop()

    backtrack(0, 0)
    return res


# DFS
def generate_parentheses(n: int) -> list[str]:
    res = []
    dfs(n, n, "", res)
    return res

def dfs(opened: int, closed: int, curr: str, res: list[str]):
    if opened == 0 and closed == 0:
        res.append(curr)
        return
    
    if opened < 0 or closed < 0 or closed < opened:
        return
    
    dfs(opened-1, closed, curr + "(", res)
    dfs(opened, closed-1, curr + ")", res)