Generate Parentheses

Q: What is the time complexity of Generate Parentheses?

The backtracking solution outputs the Catalan number C(n) = (2n)! / ((n+1)! n!) of strings, which grows like 4^n / (n^1.5 √π) . Each string has length 2n and the search never wastes a branch, so the total time is O(4^n / √n) . The extra space is O(n) for the current string and the call stack, plus the output.

Q: How many valid parentheses strings are there for n pairs?

Exactly the nth Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1,430 for n from 1 to 8. One way to see it: every well-formed string is ( + A + ) + B, where the first ( is matched by that ) , and A and B are well formed with n-1 pairs between them. Summing over the size of A gives the Catalan recurrence.

Q: Why does closed < opened guarantee a valid string?

A string goes wrong exactly when a ) arrives with no unmatched ( before it, which is when the count of ) would pass the count of ( . Allowing ) only while closed < opened stops that from ever happening, and allowing ( only while opened < n makes both counts reach n at length 2n . Together the two rules describe every prefix of a well-formed string.

Q: Can Generate Parentheses be solved without recursion?

Yes. Keep a stack of partial states, each a string with its two counters, and extend a state with the same two rules. If you push the ) extension before the ( extension, the ( one is popped first and the output stays sorted. The work is the same; the bookkeeping moves from the call stack to your own stack.

MediumBacktracking Recursion

+10

A string of parentheses is well formed when, read from left to right, the number of ) never gets ahead of the number of (, and the two counts are equal at the end. So (())() is well formed, while ())( is not: its third character closes a pair that was never opened.

You get an integer n. Return every well-formed string made of n opening and n closing parentheses, sorted in lexicographic order, where ( comes before ).

Function

generateParenthesis(n: integer) → string-array

ninteger: the number of pairs of parentheses
Returnsstring-array: every well-formed string of n pairs, in lexicographic order

Constraints

1 ≤ n ≤ 8
For n = 8 the answer holds 1,430 strings.

Examples

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explanation: Three pairs can be arranged in five well-formed ways. ((())) opens all three before closing any, and since ( sorts first it leads the list; ()()() closes each pair at once and comes last.

Input: n = 1
Output: ["()"]
Explanation: One pair has a single well-formed arrangement. The only other string of one ( and one ) is )(, which closes before anything is open.

+10 hidden tests on Submit

Follow-up

Can you count the well-formed strings for n pairs without generating them?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Only a small share of the strings of length 2n are well formed: 5 of the 64 strings for n = 3, and 1,430 of 65,536 for n = 8. The idea that cracks it is to build the string from left to right and only ever add a character that keeps it valid, so the search never enters a branch that cannot finish. Two counters decide what is allowed: how many ( you have placed, and how many ). Trying ( before ) at every step makes the strings come out already sorted.

Build every string, then check it

Intuition

The direct way is to fill the 2n positions in every possible way and keep the strings that are well formed. Each position holds ( or ), so there are 2^(2n) = 4^n strings. A recursive function places ( at the next position, recurses, then places ) there and recurses again, and every finished string goes through a check.

The check walks the string with a balance: plus 1 for (, minus 1 for ). The string is well formed when the balance never drops below 0 and ends at 0. A drop below 0 is a ) with nothing open to close, as at the third character of ())(.

Trying ( before ) at every position lists the strings in lexicographic order, because ( sorts before ). So the kept strings are already sorted.

The cost is 4^n strings, each checked in O(n). For n = 8 that is 65,536 strings for 1,430 answers, so about 98% of the work is thrown away. It finishes here because n is at most 8, but it grows fourfold with every extra pair, and it keeps building strings that start with ) although the first character already rules them out.

Algorithm

Keep a buffer of 2n characters and a list for the answers.
Write fill(pos). If pos equals 2n, check the buffer and save it if it is well formed.
Otherwise put ( at pos and call fill(pos + 1), then put ) there and call it again.
To check a string, add 1 for each ( and subtract 1 for each ). Reject it as soon as the balance goes below 0, or if it does not end at 0.
Call fill(0) and return the saved strings, already sorted.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Backtrack on open and close counts

Intuition

Move the check into the building. A prefix can still grow into a well-formed string exactly when two rules hold: it uses at most n opening parentheses, and it never has more ) than (. So at each step you may add ( while opened < n, and ) while closed < opened. When the string reaches length 2n, both counts are n and the string is well formed, with nothing left to check.

Here is the whole tree for n = 2. From the empty string only ( is allowed, since nothing is open yet. From ( both are allowed. Down the (( branch, opened is already 2, so only ) fits, twice, giving (()). Down the () branch, nothing is open, so only ( fits, then ), giving ()(). Every branch ends at an answer: the search never builds a string it has to throw away.

No answer is missed. Every prefix of a well-formed string obeys both rules, so the search never refuses the character that string needs next, and each string is produced once, since its characters spell out a single path through the tree. The order works as in the first approach: two strings first differ where their paths split, and the ( branch there is explored first.

Every leaf is an answer, and the number of answers for n pairs is the Catalan number C(n), which grows like 4^n / (n^1.5 √π). Each internal node lies on the way to at least one leaf, so there are at most 2n internal nodes per answer, and copying an answer costs O(n). The total is O(n × C(n)) = O(4^n / √n): for n = 8, 1,430 strings built directly instead of 65,536 checked.

Algorithm

Keep the string being built and two counters, opened and closed, both 0.
If the string has length 2n, save a copy of it and return.
If opened < n, add (, recurse with opened + 1, and remove it.
If closed < opened, add ), recurse with closed + 1, and remove it.
Start from the empty string and return the saved strings, already sorted because ( is tried first.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Pitfalls and edge cases

The rules fit in two comparisons, so the bugs hide in those comparisons and in the order of the two branches.

Allowing ) while closed < n instead of closed < opened builds strings such as ())(, which close a pair that was never opened.
Checking only that a string holds as many ( as ) accepts )(. The balance has to stay at 0 or above at every step, not only at the end.
Trying ) before ( produces the right strings in reverse order, and the comparison with the sorted answer fails.
Saving the shared buffer instead of a copy, in a language where lists or string builders are mutable: every saved answer then points at the same buffer, which the backtracking empties again.
Sizing a fixed result array for 2n answers, or any small guess: n = 8 has 1,430 answers. Grow the array, or compute the Catalan number first.

Frequently asked questions4

What is the time complexity of Generate Parentheses?

The backtracking solution outputs the Catalan number C(n) = (2n)! / ((n+1)! n!) of strings, which grows like 4^n / (n^1.5 √π). Each string has length 2n and the search never wastes a branch, so the total time is O(4^n / √n). The extra space is O(n) for the current string and the call stack, plus the output.

How many valid parentheses strings are there for n pairs?

Exactly the nth Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1,430 for n from 1 to 8. One way to see it: every well-formed string is ( + A + ) + B, where the first ( is matched by that ), and A and B are well formed with n-1 pairs between them. Summing over the size of A gives the Catalan recurrence.

Why does closed < opened guarantee a valid string?

A string goes wrong exactly when a ) arrives with no unmatched ( before it, which is when the count of ) would pass the count of (. Allowing ) only while closed < opened stops that from ever happening, and allowing ( only while opened < n makes both counts reach n at length 2n. Together the two rules describe every prefix of a well-formed string.

Can Generate Parentheses be solved without recursion?

Yes. Keep a stack of partial states, each a string with its two counters, and extend a state with the same two rules. If you push the ) extension before the ( extension, the ( one is popped first and the output stays sorted. The work is the same; the bookkeeping moves from the call stack to your own stack.

Python

def generateParenthesis(n):
    # Write code here

Test cases

Case 1

Case 2

Input

n = 3

Expected

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