#22 Generate Parentheses

Mediumsolve on LeetCode ↗

frequently reported atWalmart Amazon Bloomberg Microsoft Google ByteDance / TikTok

the problem

In plain words

Given n pairs of parentheses, return all well-formed (balanced) combinations.

in n = 3

out ["((()))","(()())","(())()","()(())","()()()"]

in n = 1

out ["()"]

1 ≤ n ≤ 8

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking with constraint pruning

You may add '(' while open < n, and ')' only while close < open. Those two rules make every branch valid — nothing is generated and then thrown away.

solutions

From brute force to optimal

Every position is '(' or ')'; check balance at the end.

Fill 2n slots with both choices recursively.
At the end, scan: balance never negative and ends at 0.

timeO(n·2²ⁿ)

2²ⁿ = 4ⁿ strings, each validated in O(n).

spaceO(n)

The char array and recursion depth (excluding output).

javajava.util.*

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<String> result = new ArrayList<>();4        generateAll(new char[2 * n], 0, result);5        return result;6    }7 8    private void generateAll(char[] chars, int pos, List<String> result) {9        if (pos == chars.length) {10            if (valid(chars)) result.add(new String(chars));11            return;12        }13        chars[pos] = '(';14        generateAll(chars, pos + 1, result);15        chars[pos] = ')';16        generateAll(chars, pos + 1, result);17    }18 19    private boolean valid(char[] chars) {20        int balance = 0;21        for (char c : chars) {22            balance += c == '(' ? 1 : -1;23            if (balance < 0) return false;   // a ')' closed nothing24        }25        return balance == 0;26    }27}

Only extend in ways that keep the prefix valid.

Length 2n → record.
If open < n: add '(' and recurse.
If close < open: add ')' and recurse.
Undo each append after its call.

timeO(4ⁿ/√n)

Only valid strings are built: the n-th Catalan number ≈ 4ⁿ/(n^1.5·√π) of them, each O(n).

spaceO(n)

Recursion depth 2n and the builder (excluding output).

javajava.util.*

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<String> result = new ArrayList<>();4        backtrack(n, 0, 0, new StringBuilder(), result);5        return result;6    }7 8    private void backtrack(int n, int open, int close, StringBuilder path, List<String> result) {9        if (path.length() == 2 * n) {         // a complete string is always valid10            result.add(path.toString());11            return;12        }13        if (open < n) {                       // we may still open a new pair14            path.append('(');15            backtrack(n, open + 1, close, path, result);16            path.deleteCharAt(path.length() - 1);17        }18        if (close < open) {                   // only close what is open → never invalid19            path.append(')');20            backtrack(n, open, close + 1, path, result);21            path.deleteCharAt(path.length() - 1);22        }23    }24}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<String> result = new ArrayList<>();4        backtrack(n, 0, 0, new StringBuilder(), result);5        return result;6    }7 8    private void backtrack(int n, int open, int close, StringBuilder path, List<String> result) {9        if (path.length() == 2 * n) {         // a complete string is always valid10            result.add(path.toString());11            return;12        }13        if (open < n) {                       // we may still open a new pair14            path.append('(');15            backtrack(n, open + 1, close, path, result);16            path.deleteCharAt(path.length() - 1);17        }18        if (close < open) {                   // only close what is open → never invalid19            path.append(')');20            backtrack(n, open, close + 1, path, result);21            path.deleteCharAt(path.length() - 1);22        }23    }24}

Replace recursion with a Deque of (prefix, open, close) states. Push ')' before '(' so '(' is explored first, like the recursion.

Push ("", 0, 0).
Pop a state; if complete, record it.
Otherwise push the allowed children.

timeO(4ⁿ / √n)

Visits the same states as the recursive version.

spaceO(n²)

The stack holds at most about 2n waiting states (one sibling per level), each with a prefix of up to 2n characters.

javajava.util.*

1class Solution {2    record State(String prefix, int open, int close) {}3 4    public List<String> generateParenthesis(int n) {5        List<String> result = new ArrayList<>();6        Deque<State> stack = new ArrayDeque<>(); // replaces the call stack7        stack.push(new State("", 0, 0));8        while (!stack.isEmpty()) {9            State s = stack.pop();10            if (s.prefix().length() == 2 * n) { result.add(s.prefix()); continue; }11            // push ')' first so '(' is popped first -> same order as the recursive version12            if (s.close() < s.open()) stack.push(new State(s.prefix() + ")", s.open(), s.close() + 1));13            if (s.open() < n) stack.push(new State(s.prefix() + "(", s.open() + 1, s.close()));14        }15        return result;16    }17}

in the room

How to say it in the interview

talk track

State the two rules first; the code is then four lines.
Explain why you never need a validity check: an invalid prefix is never created.
Name the Catalan numbers (1, 1, 2, 5, 14, 42 …) — it shows you know why the count grows like 4ⁿ/n^1.5.
If asked "where's the stack?": recursion uses the call stack; show the explicit Deque version.

traps

Forgetting to remove the last character after the recursive call (with a shared StringBuilder).
Allowing ')' when close < n instead of close < open — that produces strings like ")(".

what they ask next

Follow-ups

Just count them?

That is the Catalan number C(n) = C(2n, n)/(n + 1), or a DP: C(n) = Σ C(i)·C(n−1−i).

Why a StringBuilder with undo instead of s + "("?

String concatenation copies the string every call. A shared builder with append/delete is O(1) amortized per step.

Valid Parenthesis String (LC 678) with '*' wildcards?

Greedy: track the range [lo, hi] of possible open counts; fail if hi < 0, clamp lo at 0, succeed if lo == 0 at the end.

before you submit

Edge cases to test

n = 1 → ["()"].
n = 8 → 1,430 strings (the 8th Catalan number), the maximum.
A ')' with nothing open, like ")(", must never appear.

practise next