Generate Parentheses

Generate all valid combinations of n pairs of parentheses using backtracking.

backtracking recursion parentheses combinations

Write a function `generate_parentheses(n: int) -> list[str]` that takes a non-negative integer `n` and returns a list of all distinct strings containing `n` pairs of balanced parentheses. The order of strings in the list does not matter. For example, if `n = 2`, the possible strings are `((()))`, `(()())`, `(())()`, `()(())`, and `()()()`? Actually for `n = 2`, the valid strings are `(())` and `()()`. Your function must return a list containing each valid string exactly once. The returned list can be in any order. If `n = 0`, return a list containing the empty string `[""]`.

Constraints

0 <= n <= 8

Example

>>> generate_parentheses(1)
['()']
>>> sorted(generate_parentheses(2))
['(())', '()()']
>>> sorted(generate_parentheses(3))
['((()))', '(()())', '(())()', '()(())', '()()()']

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of building the string character by character, keeping track of how many open and close parentheses have been placed.

You can add an opening parenthesis as long as open count < n. You can add a closing parenthesis as long as close count < open count.

Backtracking: append a character, recurse, then remove it to try the next option.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.