Q35: Generate Parentheses. - DSA Patterns (Multi-Lang)

In Simple Words: Backtracking with two counters:

Add ( if open < n.
Add ) if close < open (never allow closing bracket without an open pair).

Time: $O(\frac{4^n}{\sqrt{n}})$ Catalan Number | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def generateParenthesis(n: int) -> list[str]:
    res = []
    def backtrack(open_c, close_c, curr):
        if len(curr) == 2 * n:
            res.append(curr)
            return
        if open_c < n:
            backtrack(open_c + 1, close_c, curr + '(')
        if close_c < open_c:
            backtrack(open_c, close_c + 1, curr + ')')
    backtrack(0, 0, "")
    return res