What is the brute force approach and complexity for Generate Parentheses?

Build all 2^(2n) strings of brackets, keep the balanced ones with time complexity O(n · 2^(2n)) and space complexity O(n).

What is the optimal approach and complexity for Generate Parentheses?

Build left to right; allow `(` while open < n and `)` only while close < open with optimal time complexity O(n · Catalan(n)) and space complexity O(n).

How do you identify the pattern for Generate Parentheses?

Look for key signals in the prompt: "generate all strings" indicates The answer is a list of complete candidates, built by choices. That is a search, not a count.; "well-formed" indicates A rule on every prefix: a `)` can only close a `(` that is still open.; "n pairs" indicates The length is fixed at 2n, and each bracket is used exactly n times. Stop when the string is complete..

Generate Parentheses

Q: How do you identify the pattern for Generate Parentheses?

Look for key signals in the prompt: "generate all strings" indicates The answer is a list of complete candidates, built by choices. That is a search, not a count.; "well-formed" indicates A rule on every prefix: a `)` can only close a `(` that is still open.; "n pairs" indicates The length is fixed at 2n, and each bracket is used exactly n times. Stop when the string is complete..

Medium·LeetCode #22Basic Anchor

LeetCode

Jump:

30-Second Mental ModelConstraint satisfaction (place one item at a time, and prune as early as possible)

Complexity:O(n · 2^(2n))→O(n · Catalan(n))

Key Insight

Keep two counters, open and close. Add ( while open < n. Add ) only when close < open, which means an unmatched ( is waiting for it. Then every prefix stays balanced, and every string that reaches length 2n is an answer.

Core Validity Invariant

A prefix is valid when close never goes above open and open never goes above n. Before each ), the rule to check is close < open, because only an unmatched ( can take it.

Problem

You are given a whole number n. Write out every string that uses exactly n opening brackets ( and n closing brackets ), and is well-formed.

Well-formed means two things. Reading from the left, the count of ( is never lower than the count of ). And at the end both counts are equal.

Return all such strings. The order does not matter.

Input

An integer n.

Output

A list of every well-formed string that has n pairs of brackets.

Example 1

Input: n = 3

Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

There are five ways to arrange three pairs. In each one, no prefix has more ) than (.

Example 2

Input: n = 1

Output: ["()"]

With one pair, the only well-formed string is ().

Constraints

• 1 ≤ n ≤ 8

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Each answer is a string of length 2n. If every place could be ( or ), how many strings would that give?
2.
Is there a string that can never become well-formed, no matter what comes after it? Look at the start of the string.
3.
While I build the string, how do I know how many ( are still waiting for a )?
4.
Can a string start with )? What does that do to the count?
5.
If I only allow choices that keep the string valid, will I ever reach a dead end and have to undo a choice?

Brute force approach

Idea

Every answer has length 2n, and each place is ( or ). So there are 2^(2n) candidates. Build all of them, then keep the ones that are balanced: a running count of ( minus ) never goes below 0, and it ends at 0.

Thinking process

1
For n = 2 the strings have length 4. Each of the 4 places can be ( or ), so there are 2⁴ = 16 candidates.
2
Test ()(): the running count goes 1, 0, 1, 0. It never goes below 0 and ends at 0, so it is kept.
3
Test )((): the count goes to −1 at the first character. It is rejected, but brute force still built all four characters before finding out.
4
Of the 16 candidates, only (()) and ()() survive.

Visual

Green = a balanced string that is kept. Red = the first character where the count of ')' passes the count of '('. Brute force builds all 16 strings for n = 2, and only 2 of them are kept.

Brute force builds every stringn = 2step 1/16

string

)

Work

strings checked: 1
of total: 16
kept: 0

prefix ) has more ')' than '(' → discard

String 1 of 16: )))). It breaks the rule, but brute force still built it.

Code & Implementation

brute.cpp

class Solution {
    // Well-formed means: no prefix has more ')' than '(', and the totals are equal.
    bool balanced(const string& s) {
        int open = 0;
        for (char ch : s) {
            open += (ch == '(') ? 1 : -1;
            if (open < 0) return false;
        }
        return open == 0;
    }

public:
    vector<string> generateParenthesis(int n) {
        vector<string> out;
        int len = 2 * n;
        // Every string of '(' and ')' with length 2n: 2^(2n) of them.
        // Bit i of mask set = '(' at position i.
        for (int mask = 0; mask < (1 << len); mask++) {
            string s(len, ')');
            for (int i = 0; i < len; i++) {
                if ((mask >> i) & 1) s[i] = '(';
            }
            if (balanced(s)) out.push_back(s);
        }
        return out;
    }
};

Complexity

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

For n = 8 that is 2^16 = 65 536 strings of length 16. Most of them have the wrong number of brackets, and the check only rejects them at the very end.

Better approach

Why brute force is slow

A string with three ( and one ) can never be balanced, yet the brute force builds and checks it anyway.

What repeated work are we doing?

Each of the 10 wrong-count strings is built to full length before the balance check throws it away.

What information can we reuse?

Count the brackets as you build. Stop a branch as soon as it would need more than n of one kind. Only strings with n of each are ever built.

New approach

Idea

Every answer has exactly n of each bracket. So stop a string as soon as one kind has n characters, and never build a string with the wrong count. The order is still free, so the balance check stays at the end.

Thinking process

1
For n = 2 the count rule keeps the strings with two ( and two ). There are C(4, 2) = 6 of them: (()), ()(), ())(, )((), )()(, ))((.
2
That drops 10 of the 16 brute-force candidates before any balance check runs.
3
The check still runs on the 6. ())( goes to −1 after three characters, and ))(( goes negative at once. They are rejected only at the end.

Code & Implementation

better.cpp

class Solution {
    bool balanced(const string& s) {
        int open = 0;
        for (char ch : s) {
            open += (ch == '(') ? 1 : -1;
            if (open < 0) return false;
        }
        return open == 0;
    }

    // Count-limited: never more than n '(' and never more than n ')'.
    // That gives exactly n of each at the end, but the order is still free,
    // so strings like ")(" are built and only rejected at the end.
    void build(string& cur, int open, int close, int n, vector<string>& out) {
        if ((int)cur.size() == 2 * n) {
            if (balanced(cur)) out.push_back(cur);
            return;
        }
        if (open < n) {
            cur.push_back('(');
            build(cur, open + 1, close, n, out);
            cur.pop_back();
        }
        if (close < n) {
            cur.push_back(')');
            build(cur, open, close + 1, n, out);
            cur.pop_back();
        }
    }

public:
    vector<string> generateParenthesis(int n) {
        vector<string> out;
        string cur;
        build(cur, 0, 0, n, out);
        return out;
    }
};

Complexity

Time O(n · C(2n, n))Space O(n)

For n = 8: C(16, 8) = 12 870 strings instead of 65 536. The balance check still runs on each one, and many of them, like ))((, are not balanced. The optimal approach stops those earlier.

Optimized approach

Idea

Start from brute force

Brute force builds all 2^(2n) strings and filters at the end. Most of that work goes into strings that can never be balanced, such as ones that start with ).

Find the repeated work

Every invalid prefix is still built to full length. If we only ever add a character that keeps the prefix valid, the invalid prefixes are never built at all.

Define the state — what variables do I need?

cur: The string built so far, one character at a time.
open: How many `(` are in `cur`. It can never be more than n.
close: How many `)` are in `cur`. It is never more than open.

Define validity

A prefix is valid when close never goes above open and open never goes above n. Before each ), the rule to check is close < open, because only an unmatched ( can take it.

Define the transitions — when does each pointer move, and why is it safe?

Before adding `(`

Allowed only while open < n

There are only n opening brackets to use.

Before adding `)`

Allowed only while close < open

There must be an unmatched ( waiting. Otherwise the string would start with ) or close one bracket too many.

When cur has 2n characters

Copy cur into the answers

Now open + close = 2n with open ≤ n and close ≤ open, so open = close = n. The string is well-formed.

What does the current window add to the answer?

Each time cur reaches length 2n, it is one answer. Nothing has to be filtered out afterwards.

Code & Implementation

optimal.cpp

class Solution {
    // open = '(' used so far, close = ')' used so far.
    // A ')' is only allowed when close < open: that keeps every prefix balanced,
    // so every finished string is valid and no work is wasted.
    void build(string& cur, int open, int close, int n, vector<string>& out) {
        if ((int)cur.size() == 2 * n) {
            out.push_back(cur);
            return;
        }
        if (open < n) {
            cur.push_back('(');
            build(cur, open + 1, close, n, out);
            cur.pop_back();
        }
        if (close < open) {
            cur.push_back(')');
            build(cur, open, close + 1, n, out);
            cur.pop_back();
        }
    }

public:
    vector<string> generateParenthesis(int n) {
        vector<string> out;
        string cur;
        build(cur, 0, 0, n, out);
        return out;
    }
};

Complexity

Time O(n · Catalan(n))Space O(n)

Every call can still be finished into an answer, so the number of calls is at most (2n + 1) times the number of answers. For n = 8 the search makes 6 917 calls for 1 430 answers. The better approach makes 48 619 calls, and the brute force checks 65 536 strings. O(n) is the string and the recursion depth. The output list is not counted in the space.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Build all 2^(2n) strings of brackets, keep the balanced ones	O(n · 2^(2n))	O(n)
Better	Build only strings with exactly n `(` and n `)`, then check balance	O(n · C(2n, n))	O(n)
Optimal	Build left to right; allow `(` while open < n and `)` only while close < open	O(n · Catalan(n))	O(n)

Why does this belong to this pattern?

Clues in the problem statement

“generate all strings”The answer is a list of complete candidates, built by choices. That is a search, not a count.
“well-formed”A rule on every prefix: a `)` can only close a `(` that is still open.
“n pairs”The length is fixed at 2n, and each bracket is used exactly n times. Stop when the string is complete.

Build one character at a time+keep two counters (open, close)+allow a choice only if the rule still holds+stop at 2n characters→Constraint satisfaction (place one item at a time, and prune as early as possible)

The rule is close < open, checked before each ). Unlike N-Queens or Sudoku, nothing has to be scanned: two counters are the whole state, so each check costs O(1). What makes it different from its neighbours is that every branch the rule allows leads to an answer, so the search never runs into a dead end and never needs to undo a wasted branch.

Don't make this mistake

Pattern confusion: allowing ')' while close < n

✗ if (close < n) { cur.push_back(')'); build(cur, open, close + 1, n, out); cur.pop_back(); }

✓ if (close < open) { cur.push_back(')'); build(cur, open, close + 1, n, out); cur.pop_back(); }

The count rule (close < n) belongs to the better approach, where strings are only counted. Used here, it lets a ) come first. On n = 2 it returns 6 strings instead of 2, and four of them are not balanced: ())(, )((), )()( and ))((. The check must compare with open, the number of ( so far.

Forgetting pop_back on the '(' branch

✗ if (open < n) { cur.push_back('('); build(cur, open + 1, close, n, out); }

✓ if (open < n) { cur.push_back('('); build(cur, open + 1, close, n, out); cur.pop_back(); }

The '(' that was added is never removed, so later strings carry it. On the dry-run input n = 3 this returns 4 strings instead of 5. ((())) is right, but ((()() appears twice and ((())( is not balanced.

Dropping the open < n check

✗ cur.push_back('('); build(cur, open + 1, close, n, out); cur.pop_back(); // no open < n test

✓ if (open < n) { cur.push_back('('); build(cur, open + 1, close, n, out); cur.pop_back(); }

Without the test, ( keeps being added past n. On n = 3 the rest of the rules still hold, so the output has 20 strings, not 5, and the first one is ((((((, which has six ( and no ).

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture