## Generate Parentheses Difficulty: Medium

#### 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

1. Brute Force: Generate all the sequences of ``` ( ``` and ``` ) ``` and check for valid ones.
2. 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))
} 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) {
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!