Loading…

mediumStack QueueLC #22Frequently asked

Generate Parentheses

Q: How do you solve Generate Parentheses using the Brute Force — Generate All, Then Filter (Baseline) approach?

When to use it: Mention to show you can define validity, then reject it for generating exponentially many invalid strings. Enumerate every length-`2n` string over `{'(', ')'}` and keep those that are balanced (running count never negative, ends at zero). **Why mention it.** It cleanly separates 'generate' from 'validate' and confirms what a valid string is. **Why we reject it.** It builds `2^(2n)` candidates but only `Catalan(n)` are valid — for `n = 8` that's `65536` candidates for `1430` answers, and the ratio worsens as `n` grows. Backtracking folds the validity check *into* generation so invalid prefixes are never extended. Time complexity: O(2^(2n) · n). Space complexity: O(2^(2n) · n).

LCPractice

Stack & Queue · 4 of 17 · 10 min

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

In plain English

We must list every string of n '(' and n ')' that is properly balanced. A string is a valid prefix as long as it never has more ')' than '(' so far, and uses at most n of each. Building characters left to right while honoring those limits yields exactly the well-formed combinations.

Examples

Example 1

Input: n = 1
Output: ["()"]
Note: Only one balanced string with a single pair.

Example 2

Input: n = 2
Output: ["(())", "()()"]
Note: The two ways to balance two pairs.

Example 3

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Note: Catalan(3) = 5 well-formed combinations.

Constraints

1 ≤ n ≤ 8

Clarifying questions4First question: Do I return all combinations or just their count?Explore questions

Q1.Do I return all combinations or just their count?
All combinations as strings. If only the count were needed, that's the n-th Catalan number — no enumeration required.
Q2.Does the order of the output list matter?
No — any order is accepted. The natural recursion (try '(' before ')') produces them in a stable lexicographic-ish order.
Q3.How large can n get?
Up to 8, so the result set is Catalan(8) = 1430 strings — small enough that the exponential output is fine.
Q4.Can there be duplicate strings in the output?
No — each leaf of the recursion builds a distinct string, so no de-duplication is needed.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Backtrack, building the string one character at a time while tracking how many '(' and ')' you've used. You may add '(' whenever open < n, and ')' only when close < open (so you never close a bracket you haven't opened). When the string reaches length 2n it's a complete valid combination. Pruning with those two counters means you only ever build valid strings — O(4ⁿ / √n) results, which is optimal since that's the count of answers.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can drive a backtracking search with the right pruning conditions so only valid states are explored, and explain why those conditions guarantee validity.

Where candidates slip

Generating all 2^(2n) strings then filtering (exponentially wasteful), or getting the close condition wrong (using close < n instead of close < open), which produces invalid strings like '))((' .

How to stand out

State the two invariants up front, explain that close < open is what enforces balance, and note the output size is the n-th Catalan number so the algorithm is output-optimal.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Generate All, Then Filter (Baseline)	`O(2^(2n) · n)`	`O(2^(2n) · n)`	Mention to show you can define validity, then reject it for generating exponentially many invalid strings.	Read
2	Backtracking with Count Pruning (Optimal)Optimal	`O(4ⁿ / √n)`	`O(n) recursion depth (plus output)`	The answer they want. State the two invariants (open < n, close < open) before coding.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewstate: cur, open, closelen(cur) == 2n?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Generate All, Then Filter (Baseline)

TimeO(2^(2n) · n)SpaceO(2^(2n) · n)

Mention to show you can define validity, then reject it for generating exponentially many invalid strings.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignoring validity, how many strings of length 2n can you form from '(' and ')'?

2Hint 2Explore hint

Generate all 2^(2n) such strings, then keep only the balanced ones using a counter check.

3Hint 3Explore hint

Correct but wasteful: most of those strings are invalid, and you still pay to build and validate each.

A · Core idea

Enumerate every length-2n string over {'(', ')'} and keep those that are balanced (running count never negative, ends at zero).

Why mention it. It cleanly separates 'generate' from 'validate' and confirms what a valid string is. Why we reject it. It builds 2^(2n) candidates but only Catalan(n) are valid — for n = 8 that's 65536 candidates for 1430 answers, and the ratio worsens as n grows. Backtracking folds the validity check into generation so invalid prefixes are never extended.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 1

"(("

ends with count 2 ≠ 0 → invalid

Statediscard

Final result["()"]

C · Code with teaching comments

Reference implementation previewpublic List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); int len = 2 * n; for (int mask = 0; mask < (1 << len); mask++) { StringBuilder sb = new StringBuilder();Explore the full code

solution.javaJava

Brute Force — Generate All, Then Filter (Baseline) — reference

3 teaching notes

1
public List<String> generateParenthesis(int n) {
2
    List<String> result = new ArrayList<>();
3
    int len = 2 * n;
4
    // Enumerate all 2^(2n) bit patterns — most yield invalid strings.
5
    for (int mask = 0; mask < (1 << len); mask++) {
6
        StringBuilder sb = new StringBuilder();
7
        for (int i = 0; i < len; i++) {
8
            sb.append(((mask >> i) & 1) == 0 ? '(' : ')');
9
        }
10
        // Filter after building — the wasteful part.
11
        if (isValid(sb.toString())) {
12
            result.add(sb.toString());
13
        }
14
    }
15
    return result;
16
}
17
 
18
private boolean isValid(String s) {
19
    int balance = 0;
20
    for (char c : s.toCharArray()) {
21
        balance += (c == '(') ? 1 : -1;
22
        // A prefix with more ')' than '(' can never be balanced.
23
        if (balance < 0) return false;
24
    }
25
    return balance == 0;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(2^(2n) · n) timeO(2^(2n) · n) spaceOpen the invariant and proofExplore the proof

Whenever brute force is 'generate everything then filter', ask whether the filter can be applied incrementally during construction. If a partial candidate can be judged invalid early, backtracking prunes whole subtrees of wasted work.

ComplexityO(2^(2n) · n) time, O(2^(2n) · n) space — There are 2^(2n) binary strings of length 2n; validating each costs O(n). The vast majority are discarded.

E · Edge cases and pitfalls2O(2^(2n)) work to produce only Catalan(n) results.Explore edge cases

Pitfalls

O(2^(2n)) work to produce only Catalan(n) results.
Building full strings before any validity check, wasting time and memory.

03.2

Approach 2 of 2 · Optimal

Backtracking with Count Pruning (Optimal)

TimeO(4ⁿ / √n)SpaceO(n) recursion depth (plus output)

The answer they want. State the two invariants (open < n, close < open) before coding.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build the string character by character. What's the rule that keeps a partial string a valid PREFIX of some balanced string?

2Hint 2Explore hint

Track open and close counts. You can add '(' while open < n; you can add ')' only while close < open.

3Hint 3Explore hint

When the length hits 2n the string is complete and necessarily valid — record it. The two count rules mean you never build an invalid prefix.

A · Core idea

Grow a candidate string left to right, recursing on the two possible next characters while enforcing constraints that keep every partial string a valid prefix.

State. Carry the current string cur and two counters: open (number of '(' placed) and close (number of ')' placed).

The two pruning invariants. (1) Add '(' only when open < n — we can never use more than n opening brackets. (2) Add ')' only when close < open — closing is allowed only if there is an unmatched opener to close. This second condition is the heart of the algorithm: it guarantees the running balance open − close is never negative, which is exactly the property that makes a prefix extendable to a balanced string. Strings like )( or ()) are never even started.

Base case. When len(cur) == 2n, we've placed n of each bracket in a valid order, so cur is a complete well-formed combination — append it to the results and return. No separate validity check is needed because the invariants guaranteed it throughout.

Why no explicit 'undo'. In the string-passing form, each recursive call receives a fresh cur + '(' or cur + ')', so there's nothing to revert — the immutability does the backtracking for us. (With a shared StringBuilder/list you'd append before recursing and delete the last character after, the classic make-move / undo-move pattern.)

Why it's optimal. You cannot do asymptotically better than producing the output, and the number of valid strings is the n-th Catalan number C(n) = (2n)! / ((n+1)! n!) ≈ 4ⁿ/(n√(πn)). Since the algorithm visits only valid prefixes (each internal node leads to at least one leaf), its running time is proportional to the output size times O(n) per string — output-optimal.

Relation to stacks. Validity here is the same invariant a stack checks in Valid Parentheses: balance never negative, zero at the end. Backtracking is effectively exploring all strings that a stack-validator would accept, generated directly rather than tested after the fact.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2

Array state

(0,0)

add '(' (open<2)

end ↓

(

[0]

Current pointerResolved stateNot processed

Final result["(())", "()()"]

C · Code with teaching comments

solution.javaJava

Backtracking with Count Pruning (Optimal) — optimal

6 teaching notes

1
public List<String> generateParenthesis(int n) {
2
    List<String> result = new ArrayList<>();
3
    // Start empty with zero opens and closes.
4
    backtrack(result, new StringBuilder(), 0, 0, n);
5
    return result;
6
}
7
 
8
private void backtrack(List<String> result, StringBuilder cur, int open, int close, int n) {
9
    // Complete string of n pairs → guaranteed valid by the invariants.
10
    if (cur.length() == 2 * n) {
11
        result.add(cur.toString());
12
        return;
13
    }
14
    // May still open a new pair.
15
    if (open < n) {
16
        // Make the move.
17
        cur.append('(');
18
        backtrack(result, cur, open + 1, close, n);
19
        // Backtrack: revert the shared StringBuilder before trying the other branch.
20
        cur.deleteCharAt(cur.length() - 1);   // undo
21
    }
22
    // Close only an already-opened bracket — the validity invariant.
23
    if (close < open) {
24
        cur.append(')');
25
        backtrack(result, cur, open, close + 1, n);
26
        cur.deleteCharAt(cur.length() - 1);   // undo
27
    }
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(4ⁿ / √n) timeO(n) recursion depth (plus output) spaceOpen the invariant and proofExplore the proof

Backtracking = DFS over partial solutions with early pruning. The reusable move is to find invariants that a partial candidate must satisfy and check them before recursing, so entire invalid subtrees are skipped. Here those invariants (open ≤ n, close ≤ open) turn an exponential filter into an output-optimal generator — the same discipline solves Subsets, Permutations, Combination Sum, and N-Queens.

ComplexityO(4ⁿ / √n) time, O(n) recursion depth (plus output) space — The recursion's leaves are exactly the Catalan(n) valid strings; each takes O(n) to assemble. Catalan(n) ≈ 4ⁿ/(n√(πn)), so total work is O(4ⁿ/√n). Recursion depth is 2n → O(n) stack space beyond the output.

E · Edge cases and pitfalls8n = 1 — Only path: '(' then ')' → ["()"]. close<open blocks a leading ')'.Explore edge cases

Edge cases handled

n = 1Only path: '(' then ')' → ["()"]. close<open blocks a leading ')'.
n = 8Produces Catalan(8) = 1430 strings; recursion depth 16, still trivial.
trying ')' firstImpossible at the root since close(0) < open(0) is false → no invalid prefix ever begins.
open == close mid-buildclose < open is false, so ')' is blocked — only '(' can extend, preventing premature closing.

Pitfalls

Using close < n instead of close < open — generates unbalanced strings like '))(('.
Forgetting to undo the StringBuilder edit in the shared-buffer version — corrupts sibling branches.
Adding a post-hoc validity filter — unnecessary and signals you didn't trust the pruning.
Recomputing counts from the string each call instead of passing them — needless O(n) work per node.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); backtrack(result, new StringBuilder(), 0, 0, n); return result; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong close condition

Allowing ')' whenever close < n (instead of close < open) lets you close brackets you never opened, producing strings like ')(' or '())(' that aren't well-formed.

Explore the code comparison

Don't write this

if close_count < n:                 # WRONG
    backtrack(cur + ')', open_count, close_count + 1)

Write this instead

if close_count < open_count:        # only close an opened bracket
    backtrack(cur + ')', open_count, close_count + 1)

Missing undo with a shared buffer

When mutating one StringBuilder across recursive calls, you must remove the character you appended after returning, or the next branch inherits stale characters.

Explore the code comparison

Don't write this

if (open < n) {
    cur.append('(');
    backtrack(result, cur, open + 1, close, n);
    // forgot to delete the appended '('
}

Write this instead

if (open < n) {
    cur.append('(');
    backtrack(result, cur, open + 1, close, n);
    cur.deleteCharAt(cur.length() - 1);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Backtracking with open/close count constraints

Code pattern to memorize

def backtrack(cur, open, close):
    if len(cur) == 2*n: res.append(cur); return
    if open < n:      backtrack(cur+'(', open+1, close)
    if close < open:  backtrack(cur+')', open, close+1)

Rules to remember

1Add '(' only while open < n — you can't open more than n pairs.
2Add ')' only while close < open — never close more than you've opened (the validity invariant).
3Base case: string length == 2n means a complete, guaranteed-valid combination → record it.
4These two count checks prune invalid branches before they're built, so no post-hoc validity check is needed.
5The recursion tree's leaves are exactly the Catalan(n) valid strings — that's why the output count is C(n) = O(4ⁿ / (n√n)).

Use this pattern when

Enumerate **all** valid combinations/configurations, not just count or check one
Choices are constrained and you can prune invalid partial states early
Balanced-structure generation: brackets, valid IPs, well-formed sequences

Choose another pattern when

You only need the *count* of valid strings → that's the Catalan number, a closed form, no enumeration
You only need to *validate* one string → that's Valid Parentheses with a stack/counter
n is large and you can't materialize all results → enumeration is exponential by nature

Interview takeaway

The key is the two counter invariants that keep every partial string a valid prefix: open ≤ n and close ≤ open. Pruning at construction time (not validating afterward) is the essence of backtracking and reappears in subsets, permutations, and combination-sum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBacktracking with constraint pruning. Recognise it when you must enumerate all valid configurations and can reject invalid partial states early. The open ≤ n / close ≤ open invariants are this problem's pruning rules; the skeleton is shared with Subsets, Permutations, and Combination Sum.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Parentheses
Validate one string with a stack — the invariant this generator enforces.
Subsets
Coming soon
Same backtracking skeleton — include/exclude each element.
Combination Sum
Coming soon
Backtracking with a running sum and a pruning bound.
Permutations
Coming soon
Backtracking with a used-set; make-move / undo-move pattern.

Same pattern

←

Evaluate Reverse Polish Notation

Continue · Next problem

Daily Temperatures

mediumStack QueueLC #22Frequently asked

Generate Parentheses

LCPractice

Stack & Queue · 4 of 17 · 10 min

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

In plain English

Examples

Example 1

Input: n = 1
Output: ["()"]
Note: Only one balanced string with a single pair.

Example 2

Input: n = 2
Output: ["(())", "()()"]
Note: The two ways to balance two pairs.

Example 3

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Note: Catalan(3) = 5 well-formed combinations.

Constraints

1 ≤ n ≤ 8

Clarifying questions4First question: Do I return all combinations or just their count?Explore questions

Q1.Do I return all combinations or just their count?
All combinations as strings. If only the count were needed, that's the n-th Catalan number — no enumeration required.
Q2.Does the order of the output list matter?
No — any order is accepted. The natural recursion (try '(' before ')') produces them in a stable lexicographic-ish order.
Q3.How large can n get?
Up to 8, so the result set is Catalan(8) = 1430 strings — small enough that the exponential output is fine.
Q4.Can there be duplicate strings in the output?
No — each leaf of the recursion builds a distinct string, so no de-duplication is needed.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can drive a backtracking search with the right pruning conditions so only valid states are explored, and explain why those conditions guarantee validity.

Where candidates slip

Generating all 2^(2n) strings then filtering (exponentially wasteful), or getting the close condition wrong (using close < n instead of close < open), which produces invalid strings like '))((' .

How to stand out

State the two invariants up front, explain that close < open is what enforces balance, and note the output size is the n-th Catalan number so the algorithm is output-optimal.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Generate All, Then Filter (Baseline)	`O(2^(2n) · n)`	`O(2^(2n) · n)`	Mention to show you can define validity, then reject it for generating exponentially many invalid strings.	Read
2	Backtracking with Count Pruning (Optimal)Optimal	`O(4ⁿ / √n)`	`O(n) recursion depth (plus output)`	The answer they want. State the two invariants (open < n, close < open) before coding.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Generate All, Then Filter (Baseline)

TimeO(2^(2n) · n)SpaceO(2^(2n) · n)

Mention to show you can define validity, then reject it for generating exponentially many invalid strings.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignoring validity, how many strings of length 2n can you form from '(' and ')'?

2Hint 2Explore hint

Generate all 2^(2n) such strings, then keep only the balanced ones using a counter check.

3Hint 3Explore hint

Correct but wasteful: most of those strings are invalid, and you still pay to build and validate each.

A · Core idea

Enumerate every length-2n string over {'(', ')'} and keep those that are balanced (running count never negative, ends at zero).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 1

"(("

ends with count 2 ≠ 0 → invalid

Statediscard

Final result["()"]

C · Code with teaching comments

solution.javaJava

Brute Force — Generate All, Then Filter (Baseline) — reference

3 teaching notes

1
public List<String> generateParenthesis(int n) {
2
    List<String> result = new ArrayList<>();
3
    int len = 2 * n;
4
    // Enumerate all 2^(2n) bit patterns — most yield invalid strings.
5
    for (int mask = 0; mask < (1 << len); mask++) {
6
        StringBuilder sb = new StringBuilder();
7
        for (int i = 0; i < len; i++) {
8
            sb.append(((mask >> i) & 1) == 0 ? '(' : ')');
9
        }
10
        // Filter after building — the wasteful part.
11
        if (isValid(sb.toString())) {
12
            result.add(sb.toString());
13
        }
14
    }
15
    return result;
16
}
17
 
18
private boolean isValid(String s) {
19
    int balance = 0;
20
    for (char c : s.toCharArray()) {
21
        balance += (c == '(') ? 1 : -1;
22
        // A prefix with more ')' than '(' can never be balanced.
23
        if (balance < 0) return false;
24
    }
25
    return balance == 0;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(2^(2n) · n) timeO(2^(2n) · n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2^(2n) · n) time, O(2^(2n) · n) space — There are 2^(2n) binary strings of length 2n; validating each costs O(n). The vast majority are discarded.

E · Edge cases and pitfalls2O(2^(2n)) work to produce only Catalan(n) results.Explore edge cases

Pitfalls

O(2^(2n)) work to produce only Catalan(n) results.
Building full strings before any validity check, wasting time and memory.

03.2

Approach 2 of 2 · Optimal

Backtracking with Count Pruning (Optimal)

TimeO(4ⁿ / √n)SpaceO(n) recursion depth (plus output)

The answer they want. State the two invariants (open < n, close < open) before coding.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build the string character by character. What's the rule that keeps a partial string a valid PREFIX of some balanced string?

2Hint 2Explore hint

Track open and close counts. You can add '(' while open < n; you can add ')' only while close < open.

3Hint 3Explore hint

When the length hits 2n the string is complete and necessarily valid — record it. The two count rules mean you never build an invalid prefix.

A · Core idea

Grow a candidate string left to right, recursing on the two possible next characters while enforcing constraints that keep every partial string a valid prefix.

State. Carry the current string cur and two counters: open (number of '(' placed) and close (number of ')' placed).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2

Array state

(0,0)

add '(' (open<2)

end ↓

(

[0]

Current pointerResolved stateNot processed

Final result["(())", "()()"]

C · Code with teaching comments

solution.javaJava

Backtracking with Count Pruning (Optimal) — optimal

6 teaching notes

1
public List<String> generateParenthesis(int n) {
2
    List<String> result = new ArrayList<>();
3
    // Start empty with zero opens and closes.
4
    backtrack(result, new StringBuilder(), 0, 0, n);
5
    return result;
6
}
7
 
8
private void backtrack(List<String> result, StringBuilder cur, int open, int close, int n) {
9
    // Complete string of n pairs → guaranteed valid by the invariants.
10
    if (cur.length() == 2 * n) {
11
        result.add(cur.toString());
12
        return;
13
    }
14
    // May still open a new pair.
15
    if (open < n) {
16
        // Make the move.
17
        cur.append('(');
18
        backtrack(result, cur, open + 1, close, n);
19
        // Backtrack: revert the shared StringBuilder before trying the other branch.
20
        cur.deleteCharAt(cur.length() - 1);   // undo
21
    }
22
    // Close only an already-opened bracket — the validity invariant.
23
    if (close < open) {
24
        cur.append(')');
25
        backtrack(result, cur, open, close + 1, n);
26
        cur.deleteCharAt(cur.length() - 1);   // undo
27
    }
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(4ⁿ / √n) timeO(n) recursion depth (plus output) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8n = 1 — Only path: '(' then ')' → ["()"]. close<open blocks a leading ')'.Explore edge cases

Edge cases handled

n = 1Only path: '(' then ')' → ["()"]. close<open blocks a leading ')'.
n = 8Produces Catalan(8) = 1430 strings; recursion depth 16, still trivial.
trying ')' firstImpossible at the root since close(0) < open(0) is false → no invalid prefix ever begins.
open == close mid-buildclose < open is false, so ')' is blocked — only '(' can extend, preventing premature closing.

Pitfalls

Using close < n instead of close < open — generates unbalanced strings like '))(('.
Forgetting to undo the StringBuilder edit in the shared-buffer version — corrupts sibling branches.
Adding a post-hoc validity filter — unnecessary and signals you didn't trust the pruning.
Recomputing counts from the string each call instead of passing them — needless O(n) work per node.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); backtrack(result, new StringBuilder(), 0, 0, n); return result; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong close condition

Allowing ')' whenever close < n (instead of close < open) lets you close brackets you never opened, producing strings like ')(' or '())(' that aren't well-formed.

Explore the code comparison

Don't write this

if close_count < n:                 # WRONG
    backtrack(cur + ')', open_count, close_count + 1)

Write this instead

if close_count < open_count:        # only close an opened bracket
    backtrack(cur + ')', open_count, close_count + 1)

Missing undo with a shared buffer

When mutating one StringBuilder across recursive calls, you must remove the character you appended after returning, or the next branch inherits stale characters.

Explore the code comparison

Don't write this

if (open < n) {
    cur.append('(');
    backtrack(result, cur, open + 1, close, n);
    // forgot to delete the appended '('
}

Write this instead

if (open < n) {
    cur.append('(');
    backtrack(result, cur, open + 1, close, n);
    cur.deleteCharAt(cur.length() - 1);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Backtracking with open/close count constraints

Code pattern to memorize

def backtrack(cur, open, close):
    if len(cur) == 2*n: res.append(cur); return
    if open < n:      backtrack(cur+'(', open+1, close)
    if close < open:  backtrack(cur+')', open, close+1)

Rules to remember

1Add '(' only while open < n — you can't open more than n pairs.
2Add ')' only while close < open — never close more than you've opened (the validity invariant).
3Base case: string length == 2n means a complete, guaranteed-valid combination → record it.
4These two count checks prune invalid branches before they're built, so no post-hoc validity check is needed.
5The recursion tree's leaves are exactly the Catalan(n) valid strings — that's why the output count is C(n) = O(4ⁿ / (n√n)).

Use this pattern when

Enumerate **all** valid combinations/configurations, not just count or check one
Choices are constrained and you can prune invalid partial states early
Balanced-structure generation: brackets, valid IPs, well-formed sequences

Choose another pattern when

You only need the *count* of valid strings → that's the Catalan number, a closed form, no enumeration
You only need to *validate* one string → that's Valid Parentheses with a stack/counter
n is large and you can't materialize all results → enumeration is exponential by nature

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Parentheses
Validate one string with a stack — the invariant this generator enforces.
Subsets
Coming soon
Same backtracking skeleton — include/exclude each element.
Combination Sum
Coming soon
Backtracking with a running sum and a pruning bound.
Permutations
Coming soon
Backtracking with a used-set; make-move / undo-move pattern.

Same pattern

←

Evaluate Reverse Polish Notation

Continue · Next problem

Daily Temperatures