Reference: LeetCode EPI 15.7

Difficulty: Medium

My Post: Java B-F & Backtracking Solutions with Detailed Explanations and Comments (easy-understand)

## Problem

Given

`n`

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

**Example:**

1 | For example, given n = 3, a solution set is: [ |

## Analysis

### Brute-Force

It is actually a backtracking method without pruning.

1 | public List<String> generateParenthesis(int n) { |

**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:**

1 | public List<String> generateParenthesis(int n) { |

**Second version:**

1 | private void backtrack(int L, int R, int n, StringBuilder sb, List<String> result) { |

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