Generate Parentheses

The Problem

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 8

The Analogy: The Mountain Trail

What are we actually searching for?

We are not searching for one best answer. We are listing every trail that uses exactly n uphill steps ( and n downhill steps ), while never dropping below ground level along the way.

That is the real shape of the problem: not "try every string and filter later," but "grow only the partial trails that are still physically possible." The moment a trail would step below ground, it stops being a candidate at all.

The Mountain Trail

Imagine a climber walking a trail made of exactly 2 * n moves. Each ( is one uphill step. Each ) is one downhill step. The climber starts at ground level, must finish back at ground level, and is never allowed to go below it.

That makes a well-formed parentheses string feel physical instead of symbolic. An opening parenthesis is not just a character. It is a step up. A closing parenthesis is not just "the other symbol." It is a step back down from height the climber has already earned.

How we define the route

While building one trail, we only need three pieces of state. route is the path we have already chosen. openCount is how many uphill steps we have spent. closeCount is how many downhill steps we have spent.

Those counts matter for different reasons. openCount < n tells us whether any uphill budget remains. closeCount < openCount tells us whether the climber is still above ground and is therefore allowed to step down. Together they define which next moves are legal from the current fork.

The safety rule that makes backtracking valid

Backtracking works here because every recursive call represents one trail prefix that is already safe. We never walk onto an impossible trail and promise to repair it later. We only extend prefixes that still obey the mountain rules.

That gives one clean invariant: 0 <= closeCount <= openCount <= n, and route is a legal partial trail. From that state, the only question is which legal next move to try first.

Testing a candidate move

Testing a move is local. If the climber still has uphill steps left, they may add (. If the climber is above ground, they may add ). If neither condition is true, that branch has reached its natural stop.

Completion is just as local. When route.length === 2 * n, the climber has used every move in the trail budget. Because the invariant already guaranteed the prefix was safe, that full route is automatically one valid answer.

How I Think Through This

I think of route as one shared trail that I keep extending and undoing. At each fork, I ask two questions in order: do I still have uphill steps left, and am I currently high enough to step back down? Those are the only two reasons a branch may continue.

I never let an invalid trail exist. If stepping down would go below ground, I simply do not take that branch. That means every recursive call starts from a route I already trust.

When the trail reaches length 2 * n, I know I have used the full budget of moves without ever breaking the safety rule, so I record route.join('') and return to the previous fork.

Take n = 3.

Building the Algorithm

Each step adds one real mountain-trail rule, then a StackBlitz exercise to lock it in.

Step 1: Build the Trail Frame and Completion Rule

Start by building the shared frame that every branch will use. generateParenthesis(n) owns results, route, and the recursive helper backtrack(openCount, closeCount). Inside that helper, the first real rule is the completion check: if route.length === 2 * n, record the current trail and return.

This step matters because it establishes what a finished trail means before we worry about how to branch. A learner should leave this step understanding that a recursive call is carrying shared state forward, and that a full-length safe route gets copied into results.

Step 2: Add the Uphill Branch

Now teach the climber how to extend the trail upward. If openCount < n, push ( onto route, recurse with openCount + 1, then pop it after the branch finishes.

This step matters because it introduces the core backtracking rhythm: choose, explore, undo. The uphill branch is the first place where the learner sees why one shared route is enough. You are not making new trail copies at every fork. You are temporarily extending the same trail, exploring everything under that choice, then restoring the earlier state.

Step 3: Add the Downhill Branch

The downhill branch is the rule that turns safe prefixes into complete legal trails. If closeCount < openCount, push ), recurse with closeCount + 1, then pop it.

This step matters because it encodes the safety invariant directly into the algorithm. closeCount < openCount means the climber is above ground right now. Without that check, the recursion would wander into impossible prefixes like \")(\". Once both guarded branches exist, the search explores every legal trail and rejects illegal ones before they spread.

Tracing through an Example

Take n = 3.

Recognizing This Pattern

• Reach for this pattern when the problem asks for all valid constructions, not one best answer, and each next choice can be declared legal or illegal immediately.
• The structural property is local validity: if a prefix is already impossible, no longer string built from it can become valid later, so pruning early is correct.
• Backtracking beats brute force here because it never builds the huge pile of invalid strings that would later be filtered out.

Common Misconceptions

"As long as I use exactly n opening and n closing parentheses, the string is valid." Total counts are not enough. A trail like )(() still goes below ground in the middle, which is already illegal.

"The downhill rule should be closeCount < n." That only says you still own some closing parentheses. It does not say there is anything available to close right now. The real rule is closeCount < openCount.

"Backtracking means fixing bad trails after they happen." Not here. The point is the opposite: only legal prefixes are allowed to keep growing.

"I do not need to pop after recursion because the call stack will clean up for me." The call stack returns control, but route is still the same shared array. If you do not pop, one branch leaks into the next branch.

Complete Solution