Generate Parentheses

A string of 2n characters is “well-formed” exactly when, read left to right, the running count of ( never falls below the running count of ), and they end equal. That rule is what lets us prune invalid branches early instead of generating all 2^(2n) strings and filtering.

Brute Force: Generate All, Then Filter

Time O(2^(2n) · n)Space O(2^(2n) · n)

Build every possible length-2n string of ( and ), and check each one for validity with a stack-based scan at the end.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        def is_valid(s):
            balance = 0
            for ch in s:
                balance += 1 if ch == '(' else -1
                if balance < 0:
                    return False
            return balance == 0

        result = []

        def build(cur):
            if len(cur) == 2 * n:
                if is_valid(cur):
                    result.append(cur)
                return
            build(cur + '(')
            build(cur + ')')

        build('')
        return result

Explores all 2^(2n) bitstrings regardless of whether a prefix is already invalid — for n = 8 that is over 65,000 candidates, almost all discarded.

Backtracking with Open/Close Counters

OptimalTime O(4^n / sqrt(n))Space O(n)

Track how many ( and ) have been placed so far. Only place ( if fewer than n have been used, and only place ) if fewer close-parens than open-parens have been used so far (i.e. there is an unmatched ( to close). This makes every partial string valid by construction, so no post-hoc check is needed.

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

        def backtrack(current, open_count, close_count):
            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

Tracing n = 2 as a decision tree. Watch how each node checks the two counters before descending: an illegal branch is pruned and never entered at all.

Current string · 0 / 4 placed

____

open0/ 2

close0/ 2

start

place (legal

open 0 < n 2

place )pruned

close 0 < open 0

Recorded results · 0 / 2

1 / 8

currentdiscardedresult

Start empty: open = 0 and close = 0. Placing ) first would push close above open, so only ( is legal.

Both n = 2 strings shown here are 2 of the 2 valid results ((()) and ()()), and the tree never visits an invalid prefix like ")(" or "))" at all — the counters rule those branches out before they are ever created.

Complexity: the number of valid sequences is the n-th Catalan number, C(n) = (1/(n+1)) · C(2n, n), which is O(4^n / n^1.5); building each takes O(n) → O(4^n / sqrt(n)) time overall. Recursion depth and the current string are bounded by 2n → O(n) auxiliary space (excluding the output).

Generate Parentheses

Brute Force: Generate All, Then Filter

Backtracking with Open/Close Counters

More Backtracking practice