Generate Parentheses

BacktrackingRecursion

MediumLeetCode #22

20 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

((()))

(()())

(())()

()(())

()()()

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

Solution

We can solve this problem using backtracking. We build the string of parentheses from left to right. At each step, we have two choices: add a left parenthesis or a right parenthesis. We need to maintain a count of open and closed parentheses to ensure the generated string is well-formed.

Algorithm Steps

Define a recursive function backtrack(currentString, openCount, closeCount).
If the length of currentString is 2 * n, we have a complete combination. Add it to the results and return.
If openCount < n, we can add an open parenthesis.
- Append ( to currentString.
- Recursively call backtrack with updated counts.
- Backtrack by removing (.
If closeCount < openCount, we can add a close parenthesis.
- Append ) to currentString.
- Recursively call backtrack with updated counts.
- Backtrack by removing ).
Initial call: backtrack("", 0, 0).

Generate Parentheses Visualization

n = 3

Progress1 / 1

Ready to start the visualization

Open Brackets

Close Brackets

Current String

Valid Combinations

No solutions found yet...

Generate Parentheses Solution


class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        res = []
        
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                res.append("".join(S))
                return
            
            if left < n:
                S.append("(")
                backtrack(S, left + 1, right)
                S.pop()
            
            if right < left:
                S.append(")")
                backtrack(S, left, right + 1)
                S.pop()

        backtrack([], 0, 0)
        return res