Medium

Generate Parentheses

LAB

Generate all well-formed parentheses strings containing n pairs, sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "n": 3
}

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

FUNCTION SHAPE

n: int→stringArray

SOLUTION NOTE

Backtracking with pruning. Only add '(' if we have remaining, only add ')' if it won't exceed open count.

Reveal reference solution +

pythonREFERENCE

def generateParenthesis(self, n: int) -> List[str]:
    res = []

    def backtrack(curr, open_count, close_count):
        if len(curr) == 2 * n:
            res.append(''.join(curr))
            return

        if open_count < n:
            curr.append('(')
            backtrack(curr, open_count + 1, close_count)
            curr.pop()

        if close_count < open_count:
            curr.append(')')
            backtrack(curr, open_count, close_count + 1)
            curr.pop()

    backtrack([], 0, 0)
    return res

TimeO(4^n / sqrt(n))

SpaceO(n)

Open on LeetCode ↗