MediumBacktrackingRecursionString

Generate Parentheses

1 approach, code in every language

You are given a whole number n that represents how many pairs of round brackets are available. Your job is to produce every distinct arrangement of these brackets that is properly balanced, meaning each opening bracket is eventually closed and no closing bracket ever appears before a matching opening one.

Return the collection of all such well-formed strings. The relative ordering of the results is not important, but each valid arrangement must appear exactly once.

Example 1

Input: n = 2

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

With two pairs there are exactly two balanced layouts: a nested pair and two side-by-side pairs.

Example 2

Input: n = 1

Output: ["()"]

A single pair can only be written one way.

Constraints

1 <= n <= 8
Every returned string has length exactly 2 * n
The count of valid results equals the nth Catalan number

Backtracking with open/close counters

Grow the string one bracket at a time, only adding a bracket when it keeps the prefix valid, and record the string once it reaches full length.

Loading animation…

Intuition

A prefix can still become a valid string as long as we have not used more opening brackets than allowed and we never close more than we have opened. By tracking the number of opening and closing brackets placed so far, we can decide at each step whether adding '(' or ')' is legal. Adding '(' is allowed whenever the count of opening brackets is still below n, and adding ')' is allowed only when there is an unmatched opening bracket. This prunes every dead branch before it starts.

Algorithm walkthrough

1Start with an empty prefix and counters open = 0 and close = 0.
2If the prefix length equals 2 * n, it is complete and balanced, so store a copy.
3If open < n, append '(' and recurse with open increased by one.
4If close < open, append ')' and recurse with close increased by one.
5Undo the last character after each recursive call so sibling branches start from the same prefix.

Implementation

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []

        def backtrack(current: str, open_count: int, close_count: int) -> None:
            if len(current) == 2 * n:
                result.append(current)
                return
            if open_count < n:
                backtrack(current + "(", open_count + 1, close_count)
            if close_count < open_count:
                backtrack(current + ")", open_count, close_count + 1)

        backtrack("", 0, 0)
        return result

Time

O(4^n / sqrt(n))

Space

O(n)

The number of valid strings is the nth Catalan number; recursion depth is bounded by 2 * n.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Ridge Walk Plans is our own problem on the technique behind Generate Parentheses: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free