Generate Parentheses

You are given an integer n — the number of pairs of parentheses at your disposal. Build every distinct well-formed string that uses exactly n opening brackets and n closing brackets, and return them all.

A string is well-formed when every ( is closed by a matching ) that comes after it — equivalently, no prefix of the string ever closes more brackets than it has opened, and the whole string ends perfectly balanced.

Return the combinations in any order.

Hints

· Stuck? Reveal one nudge at a time.

Could you build the strings one character at a time? At each position there are only two characters you could possibly place.

Not every prefix can grow into a valid string. What must be true about the counts of ( and ) in any prefix that is still worth continuing?

Keep two counters: openers used and closers used. Place ( while openers < n; place ) while closers < openers. Recurse, then undo the choice — every string that reaches length 2n is automatically valid.

Common doubts

The rules maintain closed <= opened <= n at every step, which means the running balance opened - closed never goes negative. When the string reaches length 2n, those inequalities force opened = closed = n — balanced and complete.

At each step the two branches place a different character next, so any two finished strings differ at the first position where their construction paths diverged. Every string is built along exactly one path.

The n-th Catalan number: 1, 2, 5, 14, 42, 132, 429, 1430 for n = 1..8. It grows like 4^n / (n^1.5 · sqrt(pi)) — exponential, but far slower than the 2^(2n) raw candidates.

Not with a single bracket type. All a stack would tell you is its height, and the height is exactly opened - closed — so two integers replace it. With multiple bracket types you would need the real stack.

Interview follow-ups

· What an interviewer asks next.

Precompute how many completions exist from each state (a Catalan-style DP over remaining openers and current balance). At each position, count the completions that start with ( — if k exceeds that, subtract and place ) instead. This walks straight to the k-th string in O(n^2).

The stock rule still limits openers, but two counters no longer suffice — a closer must match the most recent unclosed opener, so you carry a real stack of open bracket types in the recursion state.

Yes — either simulate the recursion with an explicit stack of (path, opened, closed) states, or build the set for n from the identity that every balanced string is ( A ) B with A and B balanced — the same decomposition that proves the Catalan count.

Fun facts

The number of valid strings is the Catalan number C(n) — the same sequence that counts binary trees with n nodes, mountain ranges drawn with up-strokes and down-strokes, and ways to cut a polygon into triangles.
The two counters opened and closed are a compressed stack: with only one bracket type, the only thing that matters about the stack is its height.
The push–recurse–pop skeleton in the optimal solution is the exact template behind Subsets, Combination Sum, Palindrome Partitioning, and N-Queens — this problem is the smallest place to learn it.

Asked at

AmazonGoogleMetaMicrosoftUberApple

Frequently Sometimes Occasionally

Example 1

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
These are the only five balanced arrangements of 3 pairs — a string like ()) ( is never produced because it closes a bracket that was never opened.

Example 2

Input: n = 1
Output: ["()"]
One pair can only be arranged one way.

Constraints

- 1 <= n <= 8

Generate Parentheses is the cleanest introduction to backtracking you will ever meet: the pruning rules are just two comparisons, yet they turn an exponential haystack into a walk that only ever touches answers. Master the idea here and Subsets, Combination Sum, and N-Queens all fall to the same template.

Prerequisites

Before you start

· Concepts used directly in the solution.

Recursion. A function that extends a partial string by one character and calls itself until the string is complete.

Balanced brackets as a running balance. Scanning left to right with +1 for an opener and -1 for a closer — a string is valid when the balance never dips below zero and ends at zero.

Backtracking. Make a choice, recurse, then undo the choice so the shared buffer is clean for the next branch.

Understand the problem

In plain English: build every string of length 2n that uses exactly n opening and n closing brackets and is properly nested — no prefix may close a bracket that was never opened. Formally, return all strings s with |s| = 2n over the alphabet () such that every prefix of s has at least as many ( as ), and the counts are equal overall.

Worked example — n = 2, candidate strings of length 4:

((((   ✗ four openers, nothing ever closes
(())   ✓
()()   ✓
())(   ✗ third char closes what is not open
)...   ✗ dead at the very first character
answer: ["(())", "()()"]

Clarifying questions

Two or three sharp questions before coding show an interviewer you think about contracts, not just code.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Can n be zero?”

If it could, the only well-formed answer would be the empty string. The constraint 1 <= n <= 8 spares us that special case — there is always at least ().

Output rules

“May I return the strings in any order?”

Yes — only the set matters, so a natural depth-first generation order is fine.

“Must every string use all n pairs?”

Yes — exactly n openers and n closers, so every answer has length exactly 2n.

Constraints and scale

“How big can n get?”

Only 8. The answer list holds at most 1430 strings, but the space of all bracket strings of length 16 is 65,536 — so generating blindly wastes about 98% of the work, and pruning pays.

The ideal opening — say it like this

Before I code, let me confirm the contract: the result can be in any order, correct?

And every string must use exactly n pairs, so all answers have length 2n.

Since n is at most 8 the output is small, but I will still generate only valid strings instead of filtering all 2 to the power 2n candidates.

Key observations

1Aha

Validity is a running balance that never dips below zero

Scan any bracket string left to right, adding +1 for ( and -1 for ). The string is well-formed exactly when the balance never goes negative and finishes at 0.

( ( ) )        ( ) ) (
1 2 1 0  ✓     1 0 -1 …  ✗ dips below zero

2Aha

You can enforce validity while building — two rules

Grow the string one character at a time, carrying two counters: opened and closed. Place ( only while opened < n (stock left). Place ) only while closed < opened (something is open to close). A prefix that would break a rule can never be repaired — so the entire subtree beneath it is skipped without ever being built.

3Aha

Every leaf of the pruned tree is an answer

The rules keep closed <= opened <= n at every step, so a string that reaches length 2n is forced to have opened = closed = n — it is valid by construction. No filtering and no duplicates either: the two branches at each step differ in the character they place next, so no string is ever produced twice. The number of leaves is the Catalan number C(n).

Brute force vs optimal

	Generate and filter	Backtracking
Time	O(2^(2n) · n)	O(4^n / √n)
Space	O(n)	O(n)

Space is measured excluding the returned list. Full code for both approaches, in all four languages, lives in the Approaches selector below.

Summary

Key takeaway

Constrained generation: encode the validity rules as pruning conditions and build only answers, instead of generating everything and filtering afterwards. Two counters — open while opened < n, close while closed < opened — are all it takes here, and the same push–recurse–pop template powers Subsets, Combination Sum, and N-Queens.

backtrack(path, opened, closed):
    if length(path) == 2n: record path; return
    if opened < n:       backtrack(path + '(', opened + 1, closed)
    if closed < opened:  backtrack(path + ')', opened, closed + 1)