Generate Parentheses

For n generate all possible of valid Parentheses

Generate Parentheses — Backtracking

Problem

Given n, generate all combinations of n pairs of parentheses that are valid.

For example, when n = 2:

["(())", "()()"]

The important part is not generating every possible string. We need to generate only the strings where:

1. We use exactly n opening parentheses.
2. We use exactly n closing parentheses.
3. At no point can we have more ) than (.

Code

var generateParenthesis = function(n) {
    let result = [];
    let output = [];

    function backtrack(leftCount, rightCount) {

        if (leftCount === n && rightCount === n) {
            result.push(output.join(''));
            return;
        }

        if (leftCount < n) {
            output.push('(');
            backtrack(leftCount + 1, rightCount);
            output.pop();
        }

        if (rightCount < leftCount) {
            output.push(')');
            backtrack(leftCount, rightCount + 1);
            output.pop();
        }
    }

    backtrack(0, 0);

    return result;
};

Core idea

This is a backtracking problem.

At every step, we make a choice:

Choose
  ↓
Explore
  ↓
Undo

For this problem:

output.push('(');        // choose
backtrack(...);          // explore
output.pop();            // undo

The same pattern is used when choosing ).

The output array represents the current path that we are building.

For example:

output = ["(", "(", ")"]

represents:

"(())"

When we reach a complete valid combination, we save it in result.

What do leftCount and rightCount mean?

They represent how many parentheses have currently been placed.

leftCount

= number of ( currently used.

rightCount

= number of ) currently used.

For example:

output = ["(", "(", ")"]

leftCount  = 2
rightCount = 1

The important thing is that these counts describe the current path, not the entire result.

The two rules

Rule 1: We can add (

if (leftCount < n)

We can keep adding opening parentheses until we have used n.

For n = 2:

leftCount = 0 → can add (
leftCount = 1 → can add (
leftCount = 2 → cannot add (

So this prevents us from having more than n opening parentheses.

Rule 2: We can add )

if (rightCount < leftCount)

This is the most important condition.

We can only add ) if we already have more ( available to match it.

For example:

output = "("

leftCount  = 1
rightCount = 0

We can add ) because:

rightCount < leftCount
0 < 1

But:

output = ")"

would be invalid because:

rightCount = 1
leftCount  = 0

1 < 0 → false

This prevents invalid strings such as:

")("
"())("
"))(("

The rule can be remembered as:

Never allow closing parentheses to become greater than opening parentheses.

Base case

if (leftCount === n && rightCount === n)

At this point we have used every parenthesis we are allowed to use.

For n = 2:

leftCount  = 2
rightCount = 2

So the path is complete.

We save it:

result.push(output.join(''));

Then return because there is nothing else to add.

Why do we need pop()?

This is the most important part of backtracking.

Suppose we have:

output = ["("]

We decide to add another (:

output.push('(');

Now:

output = ["(", "("]

We explore everything possible from here.

Eventually that branch is finished.

We need to go back to:

output = ["("]

That's what:

output.pop();

does.

So:

output.push('(');
backtrack(...);
output.pop();

means:

Put '(' in the current path
        ↓
Explore every possibility from here
        ↓
Remove '(' so we can try another possibility

Without pop(), the next branch would start with the old branch's characters.

Dry Run for n = 2

Initial state:

n = 2
output = []
leftCount = 0
rightCount = 0

Call:

backtrack(0, 0)

Step 1

Current state:

left  = 0
right = 0
output = ""

Can we add (?

leftCount < n
0 < 2 → yes

So:

output.push('(')
backtrack(1, 0)

Now:

output = "("
left  = 1
right = 0

Step 2

At:

backtrack(1, 0)

We can add another (:

1 < 2 → yes

So:

output.push('(')
backtrack(2, 0)

Now:

output = "(("
left  = 2
right = 0

Step 3

At:

backtrack(2, 0)

Can we add (?

leftCount < n
2 < 2 → false

So no more (.

Can we add )?

rightCount < leftCount
0 < 2 → true

So add ):

output = "(()"
left  = 2
right = 1

Call:

backtrack(2, 1)

Step 4

Current state:

output = "(()"
left  = 2
right = 1

Can't add (:

2 < 2 → false

Can add ):

1 < 2 → true

So:

output = "(())"
left  = 2
right = 2

Call:

backtrack(2, 2)

Now the base case is reached:

leftCount === n
rightCount === n

So we save:

(()) 

Result:

["(())"]

Step 5: Backtrack

The recursive call finishes.

We return to:

output = "(()"

Then:

output.pop();

removes the last ):

output = "(("

We return again and eventually remove the second (:

output = "("

This is important because now we can explore a different branch.

Step 6: Try ) after the first (

We are back at:

left  = 1
right = 0
output = "("

We already explored:

"("
  ↓
"(("

Now we try the other possible choice.

Can we add )?

rightCount < leftCount
0 < 1 → true

So:

output = "()"
left  = 1
right = 1

Call:

backtrack(1, 1)

Step 7

Current state:

output = "()"
left  = 1
right = 1

Can we add (?

1 < 2 → true

So:

output = "()("
left  = 2
right = 1

Call:

backtrack(2, 1)

Step 8

We cannot add another (:

2 < 2 → false

We can add ):

1 < 2 → true

So:

output = "()()"
left  = 2
right = 2

Base case is reached.

Save:

()()

Result is now:

["(())", "()()"]

Full recursion tree

The recursion can be visualized like this:

                         ""
                         |
                        "("
                       /   \
                     "(("   "()"
                     |       |
                    "(()"   "()("
                     |       |
                   "(())"   "()()"

The leaves are the complete valid combinations:

(()) 
()()

State table

For n = 2:

The key mental model

Think of the recursion as building a path one character at a time.

At every position:

Can I put '('?
    ↓
Yes → explore it → undo it

Can I put ')'?
    ↓
Yes → explore it → undo it

But the choices are restricted by two rules:

leftCount < n

controls how many ( we can use.

And:

rightCount < leftCount

controls when ) is allowed.

So the entire algorithm is essentially:

Build a path
    ↓
Only make valid choices
    ↓
When complete, save it
    ↓
Undo the choice
    ↓
Try the next choice

Difference from permute

The backtracking pattern is the same:

choose → explore → undo

But what we are tracking is different.

For permutations:

[nums[start], nums[i]] = [nums[i], nums[start]]
generatePermute(start + 1)
[nums[start], nums[i]] = [nums[i], nums[start]]

We modify the array using swap → recurse → swap back.

For parentheses:

output.push('(')
backtrack(...)
output.pop()

We modify the path using push → recurse → pop.

So the reusable backtracking pattern is:

Modify shared state
        ↓
Recursive call
        ↓
Restore shared state

The main thing to recognize in future problems is not specifically push() and pop(). It is the idea of:

Make a choice → recursively explore that choice → undo the choice → try another choice.