October 2Medium

Generate parentheses

Dynamic Programming
Backtracking
Bracket Sequences

Problem

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

Solution

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        res = []
        def backtrack(string, opened, closed):
            if opened > n or closed > n or closed > opened:
                return
            if opened == closed == n:
                res.append(string)
                return
            backtrack(string + "(", opened + 1, closed)
            backtrack(string + ")", opened, closed + 1)

        backtrack("", 0, 0)
        return res