22. Generate Parentheses

Reformulated question¶

Generate all strings of length 2n made of n '(' and n ')' such that every prefix has at least as many '(' as ')'.

Example:

n = 3
-> ["((()))", "(()())", "(())()", "()(())", "()()()"]

Key trick¶

Build only valid prefixes.

Add '(' while you still have some left.
Add ')' only when it cannot make the prefix invalid, so when right > left.

This prunes invalid branches early instead of generating everything and filtering later.

Trap¶

Common mistakes:

Generate all \(2^{2n}\) strings, then validate them.
Use a stack validator on every complete candidate.
Forget the prefix rule:
- if at any point ) are more than (, the path is already impossible.
Mutate left and right inside a loop and accidentally reuse corrupted state.

Why is this question interesting?¶

It is a clean backtracking problem where the main idea is not recursion itself, but pruning with invariants.

It tests whether you can turn a validator into a generator.
It introduces Catalan-number output while keeping the code short.

Solve the problem with idiomatic python¶

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

        def backtrack(left: int, right: int) -> None:
            # left: number of '(' still available
            # right: number of ')' still available
            if left == 0 and right == 0:
                result.append("".join(path))
                return

            # We can always place '(' if any remain.
            if left > 0:
                path.append("(")
                backtrack(left - 1, right)
                path.pop()

            # We can place ')' only if there are more ')' remaining than '('.
            # That means we already placed more '(' than ')', so the prefix stays valid.
            if right > left:
                path.append(")")
                backtrack(left, right - 1)
                path.pop()

        backtrack(n, n)
        return result

Complexity:

Time: \(O(C_n \cdot n)\) where \(C_n\) is the \(n\)th Catalan number.
Space: \(O(n)\) recursion depth, excluding output.

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, ["()"]),
        (2, ["(())", "()()"]),
        (3, ["((()))", "(()())", "(())()", "()(())", "()()()"]),
        (
            4,
            [
                "(((())))",
                "((()()))",
                "((())())",
                "((()))()",
                "(()(()))",
                "(()()())",
                "(()())()",
                "(())(())",
                "(())()()",
                "()((()))",
                "()(()())",
                "()(())()",
                "()()(())",
                "()()()()",
            ],
        ),
    ],
)
def test_generateParenthesis(n, expected):
    assert Solution().generateParenthesis(n) == expected

Comment my solution¶

Your current solution is brute force with extra duplication, so it explodes.

You generate many repeated paths by looping over a list like:

["(" for _ in range(left)] + [")" for _ in range(right)]

Those repeated '(' are indistinguishable, so you explore the same state many times.
Then you validate only at the end, which misses the key pruning rule.
The set hides duplicates but does not fix the wasted work.

is_valid is also not ideal for this task.

It checks full strings after generation.
In backtracking, validity should be enforced during generation, not after.

A small interview-friendly fix is:

Stop thinking in terms of "which parenthesis from a bag do I pick".
Think in terms of "can I place '(' or ')' now while keeping the prefix valid".

## Solution
# Time Limit Exceeded
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        def is_valid(comb):
            # "((()))" -> True
            # "(()))(" -> False
            stack = []
            for p in comb:
                if p == "(":
                    stack.append(p)
                    continue
                if stack and stack[-1] == "(":
                    stack.pop()
            return stack == []

        combinations = set()
        path = []

        def dfs(left, right):
            if left == right == 0:
                if is_valid(path):
                    combinations.add("".join(path))
                return

            rg = ["(" for _ in range(left)] + [")" for _ in range(right)]

            for p in rg:

                path.append(p)
                if p == "(":
                    left -= 1
                else:
                    right -= 1

                dfs(left, right)

                if p == "(":
                    left += 1
                else:
                    right += 1
                path.pop()

        dfs(n, n)
        return list(combinations)

Solution().generateParenthesis(2) # ['(())', '()()']
Solution().generateParenthesis(3) # ['()()()', '((()))', '(()())', '(())()', '()(())']
Solution().generateParenthesis(6) # Time Limit Exceeded