Leetcode - 22. Generate Parentheses

Medium

Dec 22, 2025

#stack

#recursion

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: ["()"]

1 <= n <= 8

Constraints:

Notes

Intuition

Well-formed parentheses follow two rules: we can add an open bracket if we haven't used all n, and we can add a close bracket only if it wouldn't exceed the number of opens. Backtracking explores all valid combinations.

Implementation

Use a recursive backtracking function tracking open count, closed count, and a stack for the current combination. Base case: when open == closed == n, we have a complete valid string—add it to results. Otherwise, if open < n, try adding an open bracket (recurse, then pop). If closed < open, try adding a close bracket (recurse, then pop).

Edge-cases

No special edge cases. The constraints (open < n and closed < open) ensure only valid combinations are generated.

Time: O(4ⁿ/√n) — the n-th Catalan number represents valid combinations
Space: O(n) — recursion depth and stack for current combination

Complexity

Solution

from typing import List

class Solution:
    def backtrack(self, open: int, closed: int, n: int, stack: List[str], result: List[str]):
        if open == closed and closed == n:
            result.append("".join(stack))
            return
        
        if open < n:
            stack.append("(")
            self.backtrack(open + 1, closed, n, stack, result)
            stack.pop()

        if closed < open:
            stack.append(")")
            self.backtrack(open, closed + 1, n, stack, result)
            stack.pop()


    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        stack = []
        self.backtrack(0, 0, n, stack, result)
        return result
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()