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: Recursively generate by going down the different possible paths to make a well-formed parentheses set. Open and closed must both equal n for it to be well-formed
Implementation: Recursive function that takes open, closed, n, stack and result. Base case open == close == n, form the string from the stack and add to result. Otherwise, check if open < n, add open to stack, recurse with new count, pop from stack after to go down other path. Check if closed < open (other path), add close to stack, recurse with new count, pop from stack.
Complexity: Time is complex, something to do with the n-th Catalan number: O(1 / (n + 1) * 2nCn * n), Space O(n) (call stack)

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()