Generate Parentheses

Q: What is the time complexity of Generate Parentheses?

Backtracking outputs C(n) = (2n)! / ((n+1)! n!) strings, the Catalan number, which grows like 4^n / (n^1.5 √π) . Each takes O(n) to build and copy, so the time is O(4^n / √n) . 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?

The nth Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1,430 for n from 1 to 8. Every well-formed string splits as ( A ) B, where that ) matches the first ( and A and B share n - 1 pairs. Summing over the size of A gives the Catalan recurrence.

Q: Can Generate Parentheses be solved without recursion?

Yes. Keep a stack of partial states, each a string with its two counters, and extend each state by the same two rules. Push the ) extension before the ( one, so the ( one is popped first and the output stays sorted.

MediumBacktracking Recursion

+10

A string of parentheses is well formed when, read from left to right, the count of ) never gets ahead of the count 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.

Given an integer n, return every well-formed string 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 make five well-formed strings. ((())) opens all three first, so it sorts first; ()()() closes each pair at once and comes last.

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

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

Few strings of length 2n are well formed: 1,430 of 65,536 for n = 8. Build each string from left to right and add a character only when the prefix can still be finished. Two counters decide that, and trying ( before ) makes the strings come out sorted.

Build every string, then check it

Intuition

Fill the 2n positions with every mix of ( and ), 4^n strings, and keep the well-formed ones. To check a string, walk it with a balance: plus 1 for (, minus 1 for ). It is well formed when the balance never drops below 0 and ends at 0. Placing ( before ) at each position lists the strings in sorted order.

Each string costs O(n) to check. For n = 8 that is 65,536 strings for 1,430 answers, so about 98% of the work is thrown away, and it grows fourfold with every extra pair.

Algorithm

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

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 grow into a well-formed string exactly when it uses at most n of ( and never has more ) than (. So ( is allowed while opened < n, and ) while closed < opened. At length 2n both counts are n, and the string is well formed with nothing left to check.

No answer is missed, because every prefix of a well-formed string obeys both rules. No branch is wasted: for n = 2, the (( branch can only close twice, giving (()), and the () branch can only open and close, giving ()(). Each string is one path through the tree, so it appears once, and the ( branch goes first, so the output is sorted.

Every leaf is an answer, so the work is proportional to the output: O(4^n / √n).

Algorithm

Keep the string being built and two counters, opened and closed, both 0.
If the string has length 2n, save a copy 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.

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

Allowing ) while closed < n instead of closed < opened. That builds ())(, which closes a pair never opened.
Checking only that the counts match at the end. That accepts )(; the balance must stay at 0 or above at every step.
Trying ) before (. The right strings come out in reverse order.
Saving the shared buffer instead of a copy, where lists or string builders are mutable. Every saved answer then shows the same buffer, which backtracking empties again.
Sizing a fixed result array by a small guess. n = 8 has 1,430 answers.

Frequently asked questions3

What is the time complexity of Generate Parentheses?

Backtracking outputs C(n) = (2n)! / ((n+1)! n!) strings, the Catalan number, which grows like 4^n / (n^1.5 √π). Each takes O(n) to build and copy, so the time is O(4^n / √n). 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?

The nth Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1,430 for n from 1 to 8. Every well-formed string splits as ( A ) B, where that ) matches the first ( and A and B share n - 1 pairs. Summing over the size of A gives the Catalan recurrence.

Can Generate Parentheses be solved without recursion?

Yes. Keep a stack of partial states, each a string with its two counters, and extend each state by the same two rules. Push the ) extension before the ( one, so the ( one is popped first and the output stays sorted.

def generateParenthesis(n):
    # Write code here

Test #1

Test #2

Argument

n = 3

Expected Output

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