LeetCode — 22. Generate Parentheses
Given
npairs of parentheses, generate all combinations of well-formed parentheses.
This is one of those problems where the final solution can look almost suspiciously simple:
if (closeUsed < openUsed) {
// we can append ')'
}
But how do you actually arrive at that condition?
That's what I want to walk through here.
Rather than jumping straight into the canonical backtracking solution, I'll start from the way I initially approached the problem — before I really understood backtracking, pruning, or even what role recursion was playing.
TL;DR
If you already understand the idea and just need a plug-and-play solution, here's the iterative version:
List<String> generateParenthesis(int n) {
final res = <String>[];
final List<(String cur, int openUsed, int closeUsed)> stack = [
('', 0, 0),
];
while (stack.isNotEmpty) {
final (cur, openUsed, closeUsed) = stack.removeLast();
if (openUsed == n && closeUsed == n) {
res.add(cur);
continue;
}
if (openUsed < n) {
stack.add((cur + '(', openUsed + 1, closeUsed));
}
if (closeUsed < openUsed) {
stack.add((cur + ')', openUsed, closeUsed + 1));
}
}
return res;
}
The number of valid combinations is the nth Catalan number:
Cₙ = 1 / (n + 1) × binom(2n, n)
= Θ(4ⁿ / n^1.5)
If s = 2n is the length of each output string and t is the number of valid combinations, then simply writing the output already requires Θ(t × s) space/time.
For the rest of this post, though, let's understand why the algorithm looks like this.
What is the problem?
You are given:
n
representing the number of pairs of parentheses.
For example:
n = 1
means we have:
(
)
and the answer is:
["()"]
For:
n = 3
we have three opening and three closing parentheses:
( ( (
) ) )
and we need to generate every arrangement that is well-formed:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
The constraints are small:
1 <= n <= 8
So a brute-force approach is actually feasible.
And that's where I started.
My first intuition: just generate everything
When I first looked at this problem, I didn't know much about backtracking or pruning.
So I thought:
If I know how to generate every possible arrangement of
nopening parentheses andnclosing parentheses, I can simply check each arrangement and keep the valid ones.
For n = 3, we're basically arranging:
( ( ( ) ) )
in every possible order.
Then:
every possible arrangement
↓
is it valid?
/ \
yes no
↓ ↓
keep discard
That gives us a very straightforward architecture.
The brute-force idea
Conceptually, I separated the problem into three responsibilities:
generate combinations
↓
when complete
↓
validate it
↓
keep if valid
In pseudocode:
generateParenthesis(n):
result = []
explorePossibleCombination(
n,
onFound: combination ->
addIfValid(combination, result)
)
return result
Then:
explorePossibleCombination(n, onFound):
...
and:
addIfValid(combination, result):
if isValidParentheses(combination):
result.add(combination)
The validator itself can be treated as a separate problem:
isValidParentheses(combination):
...
I like this separation because it lets me solve one problem at a time.
First:
How do I enumerate the possibilities?
Then:
How do I recognize a valid answer?
Generating all possibilities
There are two choices at every position:
(
)
So we can recursively build the string.
But we also need to keep track of how many of each character we've used.
For example:
current = "(()"
openUsed = 2
closeUsed = 1
For n = 3, we can continue adding characters as long as:
openUsed < 3
closeUsed < 3
The basic recursion therefore looks like:
explore(current, openUsed, closeUsed):
if openUsed == n && closeUsed == n:
we found a complete arrangement
return
if openUsed < n:
explore(current + "(", openUsed + 1, closeUsed)
if closeUsed < n:
explore(current + ")", openUsed, closeUsed + 1)
Notice something important:
At this stage, we don't care whether the parentheses are valid.
We're deliberately generating all arrangements.
A small visualization
For n = 2, the search looks roughly like this:
""
/ \
"(" ")"
/ \ \
"((" "()" ")("
/ \ \ \
"(()" "(())" "()(" ")()"
| |
" (())" "()()"
The exact tree contains every possible arrangement of two ( and two ).
Some branches will eventually produce valid strings.
Others will produce invalid strings.
Our brute-force solution doesn't care.
It explores them anyway.
Validating the completed combinations
Now we need to answer:
Is this sequence of parentheses well-formed?
A standard way to think about this is with a stack.
Whenever we see:
(
we expect a future:
)
So we can push ) onto a stack.
When we see ):
- if there is nothing available to match it → invalid
- otherwise → pop the expected
)
For example:
(())
can be processed as:
( → push )
( → push )
) → pop
) → pop
The stack is empty at the end, so the string is valid.
One possible implementation is:
bool checkWellForm(String s) {
final int n = s.length;
if (n.isOdd) return false;
final stack = List<int>.filled(n, 0);
int top = 0;
for (int i = 0; i < n; i++) {
final int c = s.codeUnitAt(i);
if (c == 0x28) {
stack[top++] = 0x29;
} else if (top == 0 || stack[--top] != c) {
return false;
}
}
return top == 0;
}
This is essentially an O(s) validation where s is the string length.
Putting the pieces together
At this point, we have a completely working solution:
typedef FoundCallback = Function(String);
class Solution {
List<String> generateParenthesis(int n) {
final result = <String>[];
explore(
n,
onFound: (combination) {
if (checkWellForm(combination)) {
result.add(combination);
}
},
);
return result;
}
void explore(
int n, {
required FoundCallback onFound,
}) {
void recursion(
String current,
int openUsed,
int closeUsed,
) {
if (openUsed == n && closeUsed == n) {
onFound.call(current);
return;
}
if (openUsed < n) {
recursion(
current + '(',
openUsed + 1,
closeUsed,
);
}
if (closeUsed < n) {
recursion(
current + ')',
openUsed,
closeUsed + 1,
);
}
}
recursion('', 0, 0);
}
bool checkWellForm(String s) {
final int n = s.length;
if (n.isOdd) return false;
final stack = List<int>.filled(n, 0);
int top = 0;
for (int i = 0; i < n; i++) {
final int c = s.codeUnitAt(i);
if (c == 0x28) {
stack[top++] = 0x29;
} else if (top == 0 || stack[--top] != c) {
return false;
}
}
return top == 0;
}
}
This is not a bad solution.
In fact, for n <= 8, it is perfectly capable of solving the problem.
Why I like the callback here
The validation inside onFound is an opinionated choice on my part.
I'm a big fan of Inversion of Control, and I find this:
explore(
n,
onFound: (combination) {
if (checkWellForm(combination)) {
result.add(combination);
}
},
);
quite readable.
The explore() function doesn't need to know what I want to do with a completed combination.
Its only responsibility is:
"I found something. Here it is."
The caller decides what happens next.
In more conventional Dart code, you might simply pass result into the recursive function and do the validation directly in the base case:
if complete:
if valid:
result.add(current)
That's probably the simpler choice for this particular LeetCode problem.
The callback is more about separation of responsibilities than algorithmic necessity.
A small Dart recursion detail
I originally experimented with writing recursive closures like this:
final recursion = (
String current,
int openUsed,
int closeUsed,
) {
...
recursion(...);
};
But Dart's definite-assignment rules don't allow a local variable to be referenced in its own initializer like that.
If you really want a recursive local closure, you can declare it first with late and assign it afterward:
late void Function(String, int, int) recursion;
recursion = (current, openUsed, closeUsed) {
// recursion(...)
};
The late tells Dart that the variable will be initialized before it is actually used.
For this case, though, a normal nested function declaration is simpler:
void recursion(
String current,
int openUsed,
int closeUsed,
) {
...
}
So that's what I would normally use.
Then LeetCode gives me a hint
At this point, we have a working solution.
But if you use LeetCode's analysis/suggestion feature, you may see an optimization suggestion along the lines of:
Prune invalid branches early by ensuring the close count never exceeds the open count during recursion.
This is where the interesting part begins.
Because now the question becomes:
Why is
closeUsed < openUsedenough to prune the search?
Rather than blindly accepting the optimization, let's derive it.
What does "prune" actually mean?
Suppose we're exploring a search tree.
Without pruning:
start
/ \
choice choice
/ \
choice choice
/ \
... ...
We keep exploring until we reach the end.
But imagine that somewhere in the tree we reach a state where we already know:
Nothing I do from here can possibly produce a valid answer.
There is no reason to explore the children of that node.
We simply stop that branch.
That's pruning.
In other words:
normal:
make choice
↓
explore
↓
explore
↓
reach dead end
↓
backtrack
With pruning:
make choice
↓
detect impossible state
↓
STOP THIS BRANCH
↓
backtrack immediately
I like thinking of it as a dead-route sign.
Instead of walking all the way down a road before discovering it's a dead end:
🚧 DEAD END
you see the sign at the entrance and turn around immediately.
So what is the dead-route sign here?
Let's look at a partial sequence:
())
We've used:
openUsed = 1
closeUsed = 2
Can this ever become a valid parentheses string?
No.
Why?
Because we have already closed more parentheses than we've opened.
And adding future characters cannot repair that prefix.
For example:
())
(((
still starts with:
())
which was already invalid.
Once the prefix is invalid in this particular way, no suffix can fix it.
Therefore:
closeUsed > openUsed
means:
This branch is dead.
And therefore we should never create it in the first place.
Deriving the pruning rule
Every prefix of a well-formed parentheses sequence must satisfy:
number of ')' <= number of '('
In our variables:
closeUsed <= openUsed
Therefore, when we are considering whether to append ):
current + ")"
we need:
closeUsed + 1 <= openUsed
Rearranging:
closeUsed < openUsed
And there is our mysterious condition:
if (closeUsed < openUsed) {
// It is safe to append ')'.
}
We didn't pull that condition out of nowhere.
We derived it from a property that every valid solution must satisfy.
That's a useful general technique for backtracking problems:
Find a property that must always be true for a valid solution. If a partial solution violates that property, prune the branch.
Backtracking vs brute force
This is also where I had to correct my own terminology.
My first recursive solution looks somewhat like a backtracking algorithm because it recursively explores a tree.
But conceptually, what I'm doing is:
generate everything
↓
validate everything afterward
That's better described as:
brute-force generation + validation
The important idea of backtracking is not recursion itself.
Instead, think:
make a choice
↓
explore that choice
↓
return from that choice
↓
try another choice
The "return" is where we back out of the previous decision and continue exploring another branch.
Recursion is simply one convenient way to implement that exploration.
The optimized solution
Now we can move the validity rule directly into the exploration.
List<String> generateParenthesis(int n) {
final result = <String>[];
_recursiveBacktracking(
result,
n,
'',
0,
0,
);
return result;
}
void _recursiveBacktracking(
List<String> result,
int n,
String current,
int openUsed,
int closeUsed,
) {
// We have constructed a complete answer.
if (openUsed == n && closeUsed == n) {
result.add(current);
return;
}
// We still have opening parentheses available.
if (openUsed < n) {
_recursiveBacktracking(
result,
n,
current + '(',
openUsed + 1,
closeUsed,
);
}
// We may only add ')' if doing so keeps
// the current prefix potentially valid.
if (closeUsed < openUsed) {
_recursiveBacktracking(
result,
n,
current + ')',
openUsed,
closeUsed + 1,
);
}
}
There are now two important rules.
Rule 1: Don't use more than n opening parentheses
if (openUsed < n)
Because we only have n pairs.
Rule 2: Don't close more parentheses than we've opened
if (closeUsed < openUsed)
Because that would make the current prefix impossible to repair.
Compare the two approaches
Brute force
generate
↓
complete string
↓
validate
↓
invalid?
↓
discard
The algorithm willingly walks into dead ends.
It only discovers the problem after reaching a complete candidate.
Backtracking + pruning
make choice
↓
is the partial state still possible?
↓
NO ──→ prune
│
YES
↓
continue
The algorithm detects the dead end as soon as it becomes logically inevitable.
That's the major optimization.
The recursive tree becomes much smaller
For example, at the beginning:
open = 0
close = 0
We cannot choose ):
close < open
0 < 0 // false
So instead of exploring:
""
/ \
"(" ")"
we immediately eliminate the invalid ")" branch:
""
|
"("
Later, if we have:
"()"
open = 1
close = 1
again:
close < open
1 < 1 // false
So we cannot create:
"())"
That branch never enters the search tree.
This is the important mental model
When learning backtracking, I find this sequence useful:
1. What choices can I make?
2. What information describes my current state?
3. What conditions must every valid solution satisfy?
4. Can a partial solution violate one of those conditions?
5. If it does, can any future choice repair it?
6. If not, prune the branch.
For this problem:
Choices
(
)
State
current
openUsed
closeUsed
Constraints
openUsed <= n
closeUsed <= n
closeUsed <= openUsed
Irrecoverable violation
closeUsed > openUsed
Therefore
When adding ):
closeUsed < openUsed
That's the reasoning that leads to the optimization.
Optional: replacing recursion with an explicit stack
Once the recursive version is completely clear, it's interesting to implement the same search iteratively.
The recursive version relies on the programming language's call stack:
_backtrack(...)
↓
_backtrack(...)
↓
_backtrack(...)
↓
return
We can manage that stack ourselves:
final stack = [
('', 0, 0),
];
Then:
while (stack.isNotEmpty) {
final state = stack.removeLast();
// process state
// add next states
}
That gives us the iterative version from the beginning of the article.
The important observation is:
Recursion isn't what makes the algorithm backtracking.
Recursion is just one way to manage the search state.
The iterative version replaces the implicit call stack with an explicit one.
One subtle point about "backtracking"
It's tempting to imagine backtracking as something like:
undo();
But it doesn't have to look that way.
In the recursive implementation, the "undo" is often represented implicitly by returning from a recursive call.
For example:
choose '('
↓
explore everything below it
↓
return
↓
the previous state is restored
↓
try ')'
With a mutable buffer, you might see the idea more explicitly:
append '('
explore
remove '('
That's why mutable lists are often useful when learning backtracking: the make → explore → undo pattern becomes physically visible.
Complexity
Let:
s = 2n
be the length of every generated answer.
The number of valid parentheses combinations is the nth Catalan number:
Cₙ = 1 / (n + 1) × binom(2n, n)
and asymptotically:
Cₙ = Θ(4ⁿ / n^1.5)
There are Cₙ output strings, each of length 2n.
Therefore, simply producing the output requires:
Θ(Cₙ × n)
time and output space.
For the optimized backtracking algorithm, the auxiliary recursion/search space is proportional to the depth of the construction:
O(n)
excluding the returned result.
One should be careful when quoting a single complexity expression for this problem because the returned output itself is already exponential in size.
Final thoughts
I think this problem is much more useful as a learning exercise if you don't start with:
"Here's the backtracking template."
Instead, start with the simpler question:
"How can I generate all possible answers?"
That naturally leads to recursion.
Then:
"How can I tell which complete answers are valid?"
That gives you validation.
Then:
"Wait — can I recognize an invalid answer before I finish constructing it?"
That's where pruning appears.
And finally:
"What property tells me that a partial answer is already impossible?"
For parentheses, the answer is:
closeUsed > openUsed
So we prevent that state from ever being created:
if (closeUsed < openUsed) {
// append ')'
}
That's the step that turns the straightforward brute-force exploration into backtracking with pruning.
The most important takeaway for me isn't the particular condition closeUsed < openUsed.
It's the reasoning pattern:
partial solution
↓
necessary condition for validity
↓
condition violated?
↓
yes → future choices cannot repair it
↓
prune
Once you start looking for those "dead-route signs," a lot of backtracking problems become much easier to reason about.
Top comments (0)