Problem statement
Generate every balanced string containing n pairs of parentheses. Each output has length 2n. For n=2, both (()) and ()() are valid, but ())( is not: a prefix closes something that has not been opened.
The original task permits 1≤n≤8. Practice on LeetCode. The empty-string result for n=0 is a useful mathematical extension, not a published input example.
Constraints & requirements
- CONTRACT
- Original task: 1≤n≤8. Track remaining brackets. A close is allowed only when close>open; this means an unmatched opening is available.
Examples 3 test cases
Example 1 Case 1
- Input
n=3- Output
["((()))","(()())","(())()","()(())","()()()"]
Five balanced strings; every prefix has at least as many opens as closes.
Example 2 Case 2
- Input
n=2- Output
[(()),()()]
Nested and adjacent pairs are both valid.
Example 3 Case 3
- Input
n=1- Output
[()]
A closing bracket cannot be the first choice.
Hints Optional
01Hint 1
Never generate a prefix that has more closing than opening brackets.
02Hint 2
With remaining counts, closes may be placed only when close>open.
03Hint 3
When both counts reach zero, store the immutable prefix.
How to think before coding
Write down whether counters mean remaining or already placed brackets. Here they mean REMAINING. An opening is allowed while open>0. A closing is allowed only when close>open, which means an unmatched opening has already been placed. Both counters reaching zero completes one string. This inequality comes from the prefix rule, not from guessing whether the previous character was an opening.
Brute force and the improvement
Generate all 2^(2n)=4^n strings of length 2n, then scan each to reject a negative balance or a nonzero final balance. Checking costs O(n·4^n) time and O(n) working space, excluding valid outputs. The waste starts as soon as a prefix closes an unopened bracket. Instead of generating the rest of that branch, reject it immediately. The improved generator keeps only legal prefixes; a shared builder is a further copy-saving optimization, described in complexity below.
Intuition: prevent invalid prefixes immediately
Checking only the final count is insufficient. )( has one open and one close but is invalid. At every prefix, placed closing brackets must not outnumber placed openings.
Your solution tracks remaining counts. If open and close both start at n, placed opens equal n-open; placed closes equal n-close. There is an unmatched opening exactly when n-open > n-close, which simplifies to close > open.
This strict inequality explains the condition without inspecting the last character. The last character alone cannot decide whether another close is legal: (()) contains two consecutive closes, and both are correct.
Algorithm
- Start with n remaining openings, n remaining closings and an empty prefix.
- Save the prefix when both counts reach zero.
- Add
(if an opening remains. - Add
)only if close>open, meaning one unmatched opening exists.
Try opening first for dictionary order with ( before ). Each concatenation creates a new String, so the parent’s prefix does not need an explicit delete operation.
Java solution
The counters represent remaining brackets. The strict close > open condition ensures that every closing bracket has an unmatched opening.
import java.util.*;
class Solution {
public static List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
brackets(n, n, "", result); // Counts mean REMAINING opening and closing parentheses.
return result;
}
private static void brackets(int open, int close, String prefix, List<String> result) {
if (open == 0 && close == 0) { // Exactly n pairs have been placed.
result.add(prefix); // Strings are immutable; no snapshot copy is needed.
return;
}
if (open > 0) brackets(open - 1, close, prefix + "(", result); // An opening is safe if available.
if (close > open) brackets(open, close - 1, prefix + ")", result); // Close only an unmatched opening.
}
public static void main(String[] args) {
System.out.println(generateParenthesis(3)); // Five strings: "((()))", "(()())", "(())()", "()(())", "()()()"
}
}For n=3 the five strings are "((()))", "(()())", "(())()", "()(())", and "()()()". Java’s list display omits the quotation marks; they are shown here to make each string’s boundary clear.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: n = 2
What to track: open and close mean counts still available, not counts already used. Each child gets a new immutable prefix string. This is the complete small traversal.
-
Only an opening is legal initially
Java operationif (open > 0) brackets(open - 1, close, prefix + "(", result);Stateroot (open=2, close=2, prefix="") creates (1,2,"(")close > open is false at the root, so a leading closing bracket never gets a child call.
-
Use the other opening
Java operationif (open > 0) brackets(open - 1, close, prefix + "(", result);State(open=0, close=2, prefix="((")No openings remain. There are two unmatched openings to close.
-
Close twice and save
Java operationif (close > open) brackets(open, close - 1, prefix + ")", result);State(0,1,"(()") → (0,0,"(())"); result = ["(())"]Each closing branch is legal because an unmatched opening exists. Both zero counts mark a complete answer.
-
Resume the one-opening prefix
Java operationif (close > open) brackets(open, close - 1, prefix + ")", result);Statewaiting frame (1,2,"(") creates (1,1,"()")The parent’s prefix is still "("; returning children never modified it. No explicit remove operation is needed.
-
Open, then close the second pair
Java operationresult.add(prefix);State(1,1,"()") → (0,1,"()(") → (0,0,"()()"); result has both stringsAt (1,1), closing is forbidden until the remaining opening is used. The final base case saves the second answer.
Final result: ["(())","()()"]
"" (open=2, close=2)
└─ "(" (1,2)
├─ "((" (0,2)
│ └─ "(()" (0,1)
│ └─ "(())" (0,0) → save
└─ "()" (1,1)
└─ "()(" (0,1)
└─ "()()" (0,0) → saveAt "()", close equals open, so another ) is blocked. The only legal next action is (. A blocked choice does not create a recursive call and should not appear as an explored tree node.
Why it works
Open is added only while available, so we never exceed n openings. Close is added only to match an existing unmatched opening, so every generated prefix is valid. The leaf uses exactly n of each. Conversely, every well-formed string obeys these same prefix conditions, so its sequence of choices is never blocked and reaches a leaf once.
Complexity and alternative approaches
There are Cₙ balanced outputs, where Cₙ is the nth Catalan number. Writing the returned characters alone costs Ω(n·Cₙ). For this valid-prefix generator, a safe bound including String concatenation is O(n²·Cₙ): there are at most O(n·Cₙ) valid-prefix nodes and creating a new prefix copies up to 2n characters. Auxiliary live string storage can be O(n²) along a deep call chain, plus O(n) frames; output uses O(n·Cₙ).
A shared StringBuilder with append, recurse and delete avoids copying each intermediate prefix and supports O(n·Cₙ) generation/copy work with O(n) auxiliary space. The immutable-string version is intentionally kept close to your code and easy to reason about for the small input bound.
Generating all 2^(2n) bracket strings and checking each one is correct but explores many invalid prefixes. Catalan DP can count balanced strings, but a count is not the requested list.
Common mistakes
- Using close≥open permits a closing bracket at the beginning.
- Forgetting whether counters mean placed or remaining reverses the inequality.
- Disallowing consecutive
)rejects valid nesting. - Saving when only one count reaches zero produces incomplete strings.