## Generate Parentheses

**Difficulty: **Medium

**Asked in: **Facebook, Microsoft

#### Understanding The Problem

**Problem Description**

Given `n`

pairs of parentheses, write a program to **generate all combinations** of balanced parentheses. You have to return a string array containing all possible cases.

**Example:**

```
Input: n = 3
Output: A solution set is
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
```

#### Solutions

**Brute Force:**Generate all the sequences of`(`

and`)`

and check for valid ones.**Backtracking:**Only add`(`

and`)`

when adding them will guarantee a solution.

You may try to solve this problem here.

#### 1. Brute Force

We can generate all sequences of `'('`

and `')'`

characters. Then, we will check if the generated sequence is valid or not.

Through recursion, we can have all the possible sequences of `(`

and `)`

. To check if the sequence is valid or not, we can do that by finding the difference between the count of `(`

and `)`

. If the difference is not zero, then clearly the sequence becomes invalid and we will discard it else, it would be a valid sequence.

**Solution Steps**

- Create a recursive function
`generateAll`

and pass a`current`

character array of size`n*2`

**(Why?)** - At each position, make 2 choices —
*set*`current[pos]`

with`(`

and go ahead in the recursion tree.**and***set*`current[pos]`

with`)`

and then go ahead in the recursion tree. - Whenever the position becomes equal to
`n*2`

then check if the`current`

character array represents a valid sequence or not. If the string is valid then add into the`combinations`

string array.

**Pseudo Code**

```
string[] generateParenthesis(int n) {
string[] combinations
char[2*n] current
generateAll(current, 0, combinations)
return combinations
}
// utility function
bool valid(char[] current) {
int balance = 0
for (char c: current) {
if (c == '(')
balance = balance + 1
else
balance = balance - 1
if (balance < 0)
return false
}
return (balance == 0)
}
void generateAll(char[] current, int pos, string[] result) {
if (pos == current.length) {
if (valid(current))
result.add(current);
} else {
current[pos] = '('
generateAll(current, pos+1, result)
current[pos] = ')'
generateAll(current, pos+1, result)
}
}
```

**Complexity Analysis**

Time Complexity: O(2^(2n)*n). For each 2^(2n) sequences, we have to validate in O(n) time.

Space Complexity: O(2^(2n)*n), including the recursion stack space.

**Critical Ideas To Think**

- Why did we initialize the size of the
`current`

character array by`2*n`

? - How did we check if the sequence in the
`current`

char array is valid or not? - In the
`generateAll`

function, why did we make the recursive call whenever we updated`current[pos]`

?

#### 2. Backtracking

In the previous case, you must have realized that we are adding `)`

in the `current`

array even though the number of `(`

is less than the number of `)`

and one can also point that at any point the number of `)`

becomes greater than the number of `(`

then the sequence will be surely invalid.

In this case, we are trying to optimize that by keeping surety that adding `(`

or `)`

in the current string will result to be a valid sequence.

It could be simply tracked by keeping the number of `(`

and `)`

placed so far. We can start an opening bracket if we still have one (of `n`

) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.

**Solution Steps**

- Create a backtrack function that updates the
`current`

string if`open_brackets`

are less than`n`

or`close_bracket`

are less than`open_bracket`

- When the length of
`current`

string becomes equal to`2*n`

, add it to the`combination`

result array.

**Pseudo Code**

```
string[] generateParenthesis(int n) {
string[] combinations
open_bracket_so_far = 0
close_bracked_so_far = 0
backtrack(combinations, "", open_bracket_so_far, close_bracked_so_far, n)
return combinations
}
// utility function
void backtrack(string[] combination, String cur, int open_br_so_far, int close_br_so_far, int n){
if (cur.length() == n * 2) {
combination.add(cur)
return
}
if (open_br_so_far < n) {
backtrack(combination, cur + "(", open_br_so_far + 1, close_br_so_far, n)
}
if (close_br_so_far < open_br_so_far) {
backtrack(combination, cur + ")", open_br_so_far, close_br_so_far + 1, n)
}
}
```

**Complexity Analysis**

Time Complexity: O((4^n)/(√n)), in simple terms, the time complexity will be the nth Catalan number.

Space Complexity:** **O((4^n)/(√n)), including recursion stack space.

**Critical Ideas To Think**

- Why is this approach called backtracking?
*Answer:*It is backtracking because we directly add`(`

or`)`

to the end of the string and directly add 1 to`open_br`

and`close_br`

- we do not explicitly restore them after each recursion. - Why the time complexity is such complex to find? Give a read about Catalan numbers.
- Why did we append
`)`

in the`cur`

string in backtracking function only when`close_br_so_far < open_br_so_far`

? - How we are finding or maintaining the count of opening brackets and closing brackets at a given state in the backtracking function?

#### Comparison of Different Approaches

#### Suggested Problems to Solve

- Letter Combinations of a Phone Number
- Valid Parentheses
- Length of longest balanced parentheses prefix
- Print all combinations of factors (Ways to factorize)
- Print combinations of distinct numbers which add up to give sum N

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**Happy Coding! Enjoy Algorithms!**