Difficulty: MediumStack

Generate Parentheses

Problem in Plain English

Given n pairs of parentheses, generate every string of n open and n close brackets that is correctly balanced. Return all distinct well-formed combinations in any order.

Problem Statement

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

A string is well-formed when every open bracket ( is eventually closed by a matching ), and at no point while scanning left to right do the closing brackets outnumber the opening ones. The count of valid strings is the n-th Catalan number, so n = 3 yields exactly 5 combinations.

Constraints

1 <= n <= 8

Examples

Example 1

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

These are all 5 well-formed strings that use exactly 3 open and 3 close brackets.

Example 2

Input: n = 1
Output: ["()"]

With a single pair there is only one balanced arrangement.

Example 3

Input: n = 2
Output: ["(())","()()"]

Two pairs may nest or sit side by side. )(() and ())( have equal totals but close an unfinished pair that does not exist; ((() leaves openers unmatched. Thus only (()) and ()() qualify.

Intuition

An opening bracket creates one unfinished pair; a closing bracket finishes the most recent unfinished pair. Track the number of unfinished pairs as a balance. For n = 3, ((())) has balances 1, 2, 3, 2, 1, 0, so every close has an opener and nothing remains unfinished. A balanced total alone is insufficient: ())(() reaches -1 before recovering. Generate choices from left to right and reject a close as soon as it would make that balance negative.

Approaches

Enumerate All Strings

Solution Details

Reveal Enumerate All Strings: intuition, complexity, and code

Intuition

Try every length-2n string, then check whether its balance stays nonnegative and finishes at zero. For n = 3, this means 64 candidates. This baseline exposes the wasted work: it still extends prefixes such as ) that no later choice can repair.

Step-by-Step Logic

Allocate a 2n-character working buffer and an empty result. In Example 1, the buffer has six slots and the first call uses pos = 0.
At each position write (, recurse to the next slot, then overwrite that slot with ) and recurse again. Only the first pos slots belong to the current prefix; the older suffix is ignored until overwritten.
At pos = 6, scan the candidate with balance = 0: add one for (, subtract one for ), and reject immediately if the balance becomes negative. Keep a string only if the full scan ends at zero.
The first leaf (((((( ends at balance 6 and is rejected. The leaf ((())) follows balances 1, 2, 3, 2, 1, 0 and is copied into the result. Every call and every leaf scan appears in the table in execution order.
After both choices at each position have returned, return the five strings ["((()))","(()())","(())()","()(())","()()()"]. A copy at each accepted leaf protects saved answers from later buffer edits.

Why It Works

Choosing each of two characters at every one of 2n positions enumerates each candidate exactly once. A negative prefix balance means a close has no earlier unmatched opener, so such a string is invalid even if later opens restore the total. A nonnegative scan ending at zero matches every close with an earlier opener and leaves none unfinished; at length 2n it therefore contains exactly n pairs. Keeping exactly the candidates satisfying these conditions produces all valid strings without duplicates.

Dry Run

Enumerate All Strings: variable states at each step
Call	pos	Current prefix	Action or leaf balance scan	Saved count
1	0	`empty`	recurse with ( then ); resume at this prefix after each child	0
2	1	`(`	recurse with ( then ); resume at this prefix after each child	0
3	2	`((`	recurse with ( then ); resume at this prefix after each child	0
4	3	`(((`	recurse with ( then ); resume at this prefix after each child	0
5	4	`((((`	recurse with ( then ); resume at this prefix after each child	0
6	5	`(((((`	recurse with ( then ); resume at this prefix after each child	0
7	6	`((((((`	1 -> 2 -> 3 -> 4 -> 5 -> 6; nonzero final: reject	0
8	6	`((((()`	1 -> 2 -> 3 -> 4 -> 5 -> 4; nonzero final: reject	0
9	5	`(((()`	recurse with ( then ); resume at this prefix after each child	0
10	6	`(((()(`	1 -> 2 -> 3 -> 4 -> 3 -> 4; nonzero final: reject	0
11	6	`(((())`	1 -> 2 -> 3 -> 4 -> 3 -> 2; nonzero final: reject	0
12	4	`((()`	recurse with ( then ); resume at this prefix after each child	0
13	5	`((()(`	recurse with ( then ); resume at this prefix after each child	0
14	6	`((()((`	1 -> 2 -> 3 -> 2 -> 3 -> 4; nonzero final: reject	0
15	6	`((()()`	1 -> 2 -> 3 -> 2 -> 3 -> 2; nonzero final: reject	0
16	5	`((())`	recurse with ( then ); resume at this prefix after each child	0
17	6	`((())(`	1 -> 2 -> 3 -> 2 -> 1 -> 2; nonzero final: reject	0
18	6	`((()))`	1 -> 2 -> 3 -> 2 -> 1 -> 0; copy and keep	1
19	3	`(()`	recurse with ( then ); resume at this prefix after each child	1
20	4	`(()(`	recurse with ( then ); resume at this prefix after each child	1
21	5	`(()((`	recurse with ( then ); resume at this prefix after each child	1
22	6	`(()(((`	1 -> 2 -> 1 -> 2 -> 3 -> 4; nonzero final: reject	1
23	6	`(()(()`	1 -> 2 -> 1 -> 2 -> 3 -> 2; nonzero final: reject	1
24	5	`(()()`	recurse with ( then ); resume at this prefix after each child	1
25	6	`(()()(`	1 -> 2 -> 1 -> 2 -> 1 -> 2; nonzero final: reject	1
26	6	`(()())`	1 -> 2 -> 1 -> 2 -> 1 -> 0; copy and keep	2
27	4	`(())`	recurse with ( then ); resume at this prefix after each child	2
28	5	`(())(`	recurse with ( then ); resume at this prefix after each child	2
29	6	`(())((`	1 -> 2 -> 1 -> 0 -> 1 -> 2; nonzero final: reject	2
30	6	`(())()`	1 -> 2 -> 1 -> 0 -> 1 -> 0; copy and keep	3
31	5	`(()))`	recurse with ( then ); resume at this prefix after each child	3
32	6	`(()))(`	1 -> 2 -> 1 -> 0 -> -1; negative: reject immediately	3
33	6	`(())))`	1 -> 2 -> 1 -> 0 -> -1; negative: reject immediately	3
34	2	`()`	recurse with ( then ); resume at this prefix after each child	3
35	3	`()(`	recurse with ( then ); resume at this prefix after each child	3
36	4	`()((`	recurse with ( then ); resume at this prefix after each child	3
37	5	`()(((`	recurse with ( then ); resume at this prefix after each child	3
38	6	`()((((`	1 -> 0 -> 1 -> 2 -> 3 -> 4; nonzero final: reject	3
39	6	`()((()`	1 -> 0 -> 1 -> 2 -> 3 -> 2; nonzero final: reject	3
40	5	`()(()`	recurse with ( then ); resume at this prefix after each child	3
41	6	`()(()(`	1 -> 0 -> 1 -> 2 -> 1 -> 2; nonzero final: reject	3
42	6	`()(())`	1 -> 0 -> 1 -> 2 -> 1 -> 0; copy and keep	4
43	4	`()()`	recurse with ( then ); resume at this prefix after each child	4
44	5	`()()(`	recurse with ( then ); resume at this prefix after each child	4
45	6	`()()((`	1 -> 0 -> 1 -> 0 -> 1 -> 2; nonzero final: reject	4
46	6	`()()()`	1 -> 0 -> 1 -> 0 -> 1 -> 0; copy and keep	5
47	5	`()())`	recurse with ( then ); resume at this prefix after each child	5
48	6	`()())(`	1 -> 0 -> 1 -> 0 -> -1; negative: reject immediately	5
49	6	`()()))`	1 -> 0 -> 1 -> 0 -> -1; negative: reject immediately	5
50	3	`())`	recurse with ( then ); resume at this prefix after each child	5
51	4	`())(`	recurse with ( then ); resume at this prefix after each child	5
52	5	`())((`	recurse with ( then ); resume at this prefix after each child	5
53	6	`())(((`	1 -> 0 -> -1; negative: reject immediately	5
54	6	`())(()`	1 -> 0 -> -1; negative: reject immediately	5
55	5	`())()`	recurse with ( then ); resume at this prefix after each child	5
56	6	`())()(`	1 -> 0 -> -1; negative: reject immediately	5
57	6	`())())`	1 -> 0 -> -1; negative: reject immediately	5
58	4	`()))`	recurse with ( then ); resume at this prefix after each child	5
59	5	`()))(`	recurse with ( then ); resume at this prefix after each child	5
60	6	`()))((`	1 -> 0 -> -1; negative: reject immediately	5
61	6	`()))()`	1 -> 0 -> -1; negative: reject immediately	5
62	5	`())))`	recurse with ( then ); resume at this prefix after each child	5
63	6	`())))(`	1 -> 0 -> -1; negative: reject immediately	5
64	6	`()))))`	1 -> 0 -> -1; negative: reject immediately	5
65	1	`)`	recurse with ( then ); resume at this prefix after each child	5
66	2	`)(`	recurse with ( then ); resume at this prefix after each child	5
67	3	`)((`	recurse with ( then ); resume at this prefix after each child	5
68	4	`)(((`	recurse with ( then ); resume at this prefix after each child	5
69	5	`)((((`	recurse with ( then ); resume at this prefix after each child	5
70	6	`)(((((`	-1; negative: reject immediately	5
71	6	`)(((()`	-1; negative: reject immediately	5
72	5	`)((()`	recurse with ( then ); resume at this prefix after each child	5
73	6	`)((()(`	-1; negative: reject immediately	5
74	6	`)((())`	-1; negative: reject immediately	5
75	4	`)(()`	recurse with ( then ); resume at this prefix after each child	5
76	5	`)(()(`	recurse with ( then ); resume at this prefix after each child	5
77	6	`)(()((`	-1; negative: reject immediately	5
78	6	`)(()()`	-1; negative: reject immediately	5
79	5	`)(())`	recurse with ( then ); resume at this prefix after each child	5
80	6	`)(())(`	-1; negative: reject immediately	5
81	6	`)(()))`	-1; negative: reject immediately	5
82	3	`)()`	recurse with ( then ); resume at this prefix after each child	5
83	4	`)()(`	recurse with ( then ); resume at this prefix after each child	5
84	5	`)()((`	recurse with ( then ); resume at this prefix after each child	5
85	6	`)()(((`	-1; negative: reject immediately	5
86	6	`)()(()`	-1; negative: reject immediately	5
87	5	`)()()`	recurse with ( then ); resume at this prefix after each child	5
88	6	`)()()(`	-1; negative: reject immediately	5
89	6	`)()())`	-1; negative: reject immediately	5
90	4	`)())`	recurse with ( then ); resume at this prefix after each child	5
91	5	`)())(`	recurse with ( then ); resume at this prefix after each child	5
92	6	`)())((`	-1; negative: reject immediately	5
93	6	`)())()`	-1; negative: reject immediately	5
94	5	`)()))`	recurse with ( then ); resume at this prefix after each child	5
95	6	`)()))(`	-1; negative: reject immediately	5
96	6	`)())))`	-1; negative: reject immediately	5
97	2	`))`	recurse with ( then ); resume at this prefix after each child	5
98	3	`))(`	recurse with ( then ); resume at this prefix after each child	5
99	4	`))((`	recurse with ( then ); resume at this prefix after each child	5
100	5	`))(((`	recurse with ( then ); resume at this prefix after each child	5
101	6	`))((((`	-1; negative: reject immediately	5
102	6	`))((()`	-1; negative: reject immediately	5
103	5	`))(()`	recurse with ( then ); resume at this prefix after each child	5
104	6	`))(()(`	-1; negative: reject immediately	5
105	6	`))(())`	-1; negative: reject immediately	5
106	4	`))()`	recurse with ( then ); resume at this prefix after each child	5
107	5	`))()(`	recurse with ( then ); resume at this prefix after each child	5
108	6	`))()((`	-1; negative: reject immediately	5
109	6	`))()()`	-1; negative: reject immediately	5
110	5	`))())`	recurse with ( then ); resume at this prefix after each child	5
111	6	`))())(`	-1; negative: reject immediately	5
112	6	`))()))`	-1; negative: reject immediately	5
113	3	`)))`	recurse with ( then ); resume at this prefix after each child	5
114	4	`)))(`	recurse with ( then ); resume at this prefix after each child	5
115	5	`)))((`	recurse with ( then ); resume at this prefix after each child	5
116	6	`)))(((`	-1; negative: reject immediately	5
117	6	`)))(()`	-1; negative: reject immediately	5
118	5	`)))()`	recurse with ( then ); resume at this prefix after each child	5
119	6	`)))()(`	-1; negative: reject immediately	5
120	6	`)))())`	-1; negative: reject immediately	5
121	4	`))))`	recurse with ( then ); resume at this prefix after each child	5
122	5	`))))(`	recurse with ( then ); resume at this prefix after each child	5
123	6	`))))((`	-1; negative: reject immediately	5
124	6	`))))()`	-1; negative: reject immediately	5
125	5	`)))))`	recurse with ( then ); resume at this prefix after each child	5
126	6	`)))))(`	-1; negative: reject immediately	5
127	6	`))))))`	-1; negative: reject immediately	5
Return	-	-	`["((()))","(()())","(())()","()(())","()()()"]`	5

Complexity Analysis

Time Complexity

O(n \cdot 4^n)

Space Complexity

O(n)

There are 2^(2n) = 4^n leaves. Scanning a leaf costs at most 2n operations, so O(n * 4^n) bounds generation plus validation; early rejection may shorten scans. The mutable buffer and recursion depth use O(n) auxiliary space. Let C_n = binomial(2n,n)/(n+1) be the number of answers. Copying and retaining C_n strings of length 2n requires Theta(n * C_n) output space and work; including that output, total retained space is O(n * C_n).

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class Solution {5    public List<String> generateParenthesis(int n) {6        List<String> result = new ArrayList<>();7        generateAll(new char[2 * n], 0, result);8        return result;9    }10
11    private void generateAll(char[] current, int pos, List<String> result) {12        if (pos == current.length) {13            if (isValid(current)) {14                result.add(new String(current));15            }16            return;17        }18        current[pos] = '(';19        generateAll(current, pos + 1, result);20        current[pos] = ')';21        generateAll(current, pos + 1, result);22    }23
24    private boolean isValid(char[] current) {25        int balance = 0;26        for (char c : current) {27            if (c == '(') balance++;28            else balance--;29            if (balance < 0) return false;30        }31        return balance == 0;32    }33}

Hints

Hint 1

A closing bracket is only legal when fewer closes than opens have been placed so far.

Hint 2

Think of building the answer one character at a time while tracking two counters, open and close.

Hint 3

Recurse with open + 1 when open is below n and with close + 1 when close is below open, recording the string once its length reaches 2n.

Edge Cases

n = 1 yields exactly one combination, so the close branch is taken exactly once per path.
Strings that close before opening, such as ")(", must be discarded the moment the balance goes negative.
The upper bound n = 8 produces 1430 strings, which fits easily in memory but already shows the Catalan growth.

Common Mistakes and Interview Tips

Allowing ) when close equals open, which builds strings like "())(()" that can never recover.
Checking only the final counts and missing prefixes where closes temporarily outnumber opens.
Forgetting the base case at length 2n, which lets the recursion append brackets forever.
Saving a mutable working buffer instead of a fresh string, or forgetting a pop after a recursive child, corrupts answers as later branches edit the same buffer. Java uses a fixed buffer: only slots before pos are part of the active prefix, and every deeper slot is overwritten before a leaf.
Calling the whole search linear because only valid strings are explored: n = 8 still returns 1430 distinct strings of length 16. Output storage cannot be omitted from a total-space claim.

Key Takeaway

Backtracking keeps a partial answer valid at every step and restores shared working storage when a choice returns. Pruning removes impossible prefixes, while the number and size of requested answers still impose exponential output work.