Reference: LeetCode EPI 15.7
Difficulty: Medium

## Problem

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

Example:

## Analysis

### Brute-Force

It is actually a backtracking method without pruning.

Time: $O(N \times 2^{2N})$
Space: $O(N \times 2^{2N})$

### Backtracking

Based on the previous brute-force solution, we actually add some code of pruning, which cuts unnecessary recursive calls in backtracking.

The core idea is that we allow L is temporarily greater than R because we can append more ) to satisfy L == R in the future.

However, we don’t allow L < R at any time to occur, e.g. ()) (L = 1, R = 2), ) (L = 0, R = 1). The reason is that it is impossible that these strings would develop to any valid strings in the future. So we should stop trying right away.

Therefore, pruning is based on this idea, so during backtracking we should not allow:

• L > n or R > n
• L < R

L and R are the numbers of ( and ).

Then we can append these conditions in the base-case section (check out the first version below).

In an opposite perspective, we allow the following situations to occur:

• L <= n and R <= n
• L >= R

In other words, when adding ( we should guarantee that L < n; when adding ) we should guarantee that R < n and L > R.

Then we can append these conditions before doing recursive calls (check out the second version below).

First version:

Second version:

Time: $O(\frac{4^N}{\sqrt{n}})$
Space: $O(\frac{4^N}{\sqrt{n}})$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.