DSA Generating Parentheses

The problem

Generate Parentheses asks for every valid string of n pairs of brackets. A valid string closes every bracket it opens. A closing bracket never appears before the opening bracket it matches.

One pair is one opening bracket and one closing bracket. The cases below run from zero pairs to three pairs. The article lists the strings in the order the search grows them, opening bracket first.

cases = [
    (0, [""]),
    (1, ["()"]),
    (2, ["(())", "()()"]),
    (3, ["((()))", "(()())", "(())()", "()(())", "()()()"]),
]
for n, expected in cases:
    print("n =", n, "strings:", expected)

The counts are 1, 1, 2 and 5. Zero pairs give one string, the empty string. Each added pair then multiplies the count by more than two.

Intuition: a running balance judges every string

The balance of a string is the count of opening brackets minus the count of closing brackets, read left to right. A valid string ends at balance zero. Its balance also never drops below zero on the way.

Hope is not a method here. A string that opens with a closing bracket breaks the second rule at its first character. No continuation can repair that start.

for text in (")(", "(()", "())(()"):
    balance = 0
    lowest = 0
    for ch in text:
        balance += 1 if ch == "(" else -1
        lowest = min(lowest, balance)
    print(text, "- final balance:", balance, "- lowest balance:", lowest)

Only the middle string passes both tests, and it still fails the first one because a bracket is left open. The two tests together are the whole validity check. The brute force applies them to every finished string.

Brute force: build every string, then test it

The brute force builds every string of length 2n over the two brackets. It tests each finished string with the balance rules. A counter records how many strings were built.

def generate_brute(n):
    results = []
    path = []
    built = [0]
    def valid(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False
        return balance == 0
    def search():
        if len(path) == 2 * n:
            built[0] += 1
            text = "".join(path)
            if valid(text):
                results.append(text)
            return
        for bracket in ("(", ")"):
            path.append(bracket)
            search()
            path.pop()
    search()
    return results, built[0]

result, built = generate_brute(3)
for row in result:
    print(row)
print("valid strings:", len(result))
print("strings built:", built)

The brute force built 64 strings to keep 5. Most builds were doomed by an early closing bracket. The brute force cannot know that until each string is complete and tested.

The optimal solution: two counters guard each placement

The state is the partial string plus two counters, opened and closed, and a bracket is placed only when its counter rule allows it, so every partial string can still become valid. That one sentence is the whole method.

An opening bracket may be placed while opened stays below n. A closing bracket may be placed only while closed stays below opened. The second rule is the balance rule, applied one step early instead of after the fact.

def generate(n):
    results = []
    path = []
    def search(opened, closed):
        if len(path) == 2 * n:
            results.append("".join(path))
            return
        if opened < n:
            path.append("(")
            search(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            search(opened, closed + 1)
            path.pop()
    search(0, 0)
    return results

cases = [
    (0, [""]),
    (1, ["()"]),
    (2, ["(())", "()()"]),
    (3, ["((()))", "(()())", "(())()", "()(())", "()()()"]),
]
for n, expected in cases:
    result = generate(n)
    print("n =", n, "->", result, "match:", result == expected)

Every case matches. No invalid string was ever completed along the way. The counters stop a bad string at its first bad bracket instead of its last one.

Walkthrough: growing both strings for n = 2

The walk prints the string and both counters after each placement. A record line marks a finished string. Watch the second string close early, as soon as the counters allow it.

n = 2
path = []
def search(opened, closed):
    if len(path) == 2 * n:
        print("record", "".join(path))
        return
    if opened < n:
        path.append("(")
        print("place ( - string:", "".join(path), "- opened:", opened + 1, "closed:", closed)
        search(opened + 1, closed)
        path.pop()
    if closed < opened:
        path.append(")")
        print("place ) - string:", "".join(path), "- opened:", opened, "closed:", closed + 1)
        search(opened, closed + 1)
        path.pop()
search(0, 0)

The first string opens twice, then closes twice. The second string opens, closes, and repeats. Both orders come from the same two counter rules, with no other machinery.

Complexity

The count of valid strings for n pairs is the nth Catalan number. Time is O(n times that count), because each valid string costs 2n placements to build and copy. The brute force instead spends its time on all 2^(2n) strings, valid or not.

Extra space is O(n) besides the stored results. The path holds at most 2n brackets, and the counters are two numbers.

catalan = [1, 1, 2, 5, 14]
for n in [2, 3, 4]:
    print("n =", n, "- brute strings built:", 2 ** (2 * n), "- valid strings:", catalan[n])

At four pairs the brute force builds 256 strings for 14 valid ones. The guarded search builds only prefixes that can still finish valid, so its work tracks the smaller column.

Edge cases and pitfalls

Zero pairs give the empty string, and one pair gives a single string. At the very start, the counters allow only an opening bracket. A closing bracket first would push closed above opened at once.

def generate(n):
    results = []
    path = []
    def search(opened, closed):
        if len(path) == 2 * n:
            results.append("".join(path))
            return
        if opened < n:
            path.append("(")
            search(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            search(opened, closed + 1)
            path.pop()
    search(0, 0)
    return results

print("n = 0:", generate(0))
print("n = 1:", generate(1))
opened = 0
closed = 0
print("at the start - can open:", opened < 3, "- can close:", closed < opened)

The classic mistake swaps the closing rule. It tests closed against n instead of against opened. That rule accepts strings that end balanced but dip below zero on the way.

text = "())(()"
balance = 0
lowest = 0
for ch in text:
    balance += 1 if ch == "(" else -1
    lowest = min(lowest, balance)
print("string:", text)
print("final balance:", balance, "- lowest balance:", lowest)
print("valid:", balance == 0 and lowest >= 0)

The string ends at balance zero, so a final-balance check alone would pass it. The lowest balance of minus 1 is the evidence against it. Both tests are needed, and the counter rule builds both in from the start.