Generate Parentheses

StackBacktracking

MediumLeetCode #22

25 min

Problem Statement

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example

Example 1:

Input: n = 3

Input n:

Generated Parentheses:

((()))

(()())

(())()

()(())

()()()

Output: ["((()))","(()())","(())()","()(())","()()()"]

Solution

This problem can be solved using backtracking. We build the string character by character, keeping track of the number of open and closed parentheses.

Algorithm Steps

Start with an empty string and counts of open and close parentheses set to 0.
If the number of open parentheses is less than n, we can add an open parenthesis and recurse.
If the number of close parentheses is less than the number of open parentheses, we can add a close parenthesis and recurse.
If the length of the string is 2 * n, we have a valid combination, so we add it to our result list.

Backtracking Path

Open: 0, Close: 0

Result

Current path: "", open: 0, close: 0

Generate Parentheses Solution


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

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return

            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res