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

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