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