How to solve: Leetcode#22 Generate parentheses

Thees2k1 — Fri, 02 Oct 2026 10:08:39 +0000

Given n pairs 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:

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 n opening parentheses and n closing 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 < openUsed enough 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.

DEV Community: Thees2k1

How to solve: Leetcode#22 Generate parentheses

TL;DR

What is the problem?

My first intuition: just generate everything

The brute-force idea

Generating all possibilities

A small visualization

Validating the completed combinations

Putting the pieces together

Why I like the callback here

A small Dart recursion detail

Then LeetCode gives me a hint

What does "prune" actually mean?

So what is the dead-route sign here?

Deriving the pruning rule

Backtracking vs brute force

The optimized solution

Rule 1: Don't use more than n opening parentheses

Rule 2: Don't close more parentheses than we've opened

Compare the two approaches

Brute force

Backtracking + pruning

The recursive tree becomes much smaller

This is the important mental model

Choices

State

Constraints

Irrecoverable violation

Therefore

Optional: replacing recursion with an explicit stack

One subtle point about "backtracking"

Complexity

Final thoughts

Rule 1: Don't use more than `n` opening parentheses