LeetCode — Generate Parentheses

Problem statement

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

Problem statement taken from: https://leetcode.com/problems/generate-parentheses

Example 1:

Input: n = 3  
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2:

Input: n = 1  
Output: ["()"]

Constraints:

- 1 <= n <= 8

Explanation

Brute force

A brute force approach to this problem is to generate all combinations of parenthesis using ( and ). Then verify which are the valid ones and add the valid ones to the result.

A small C++ code snippet of the above logic will look as below:

vector<string> generateParenthesis(int n) {  
    vector<string> combinations;  
    generateAll("", 0, combinations);  
    return combinations;  
}  

void generateAll(string current, int pos, vector<string> result) {  
    if (pos == current.length) {  
        if (valid(current))  
            result.add(string(current));  
    } else {  
        current += '(';  
        generateAll(current, pos+1, result);  
        current += ')';  
        generateAll(current, pos+1, result);  
    }  
}  

bool valid(string current) {  
    int balance = 0;  
    for (int i = 0; i < current.length; i++) {  
        if (current[i] == '(') balance++;  
        else balance--;  
        if (balance < 0) return false;  
    }  
    return balance == 0;  
}

The time complexity of the above program is O((2²n)*n).

Backtracking

We can avoid generating all possible permutations of parenthesis by using backtracking approach.

Instead of adding ( or ) every time as in the above approach, we add them only when we know it will remain a valid sequence. To do this, we can keep track of the number of opening and closing brackets we have added so far.

Algorithm

- initialize result array.  

- call _generateParenthesis("", n, 0, 0, result)  
  - This is a recursive function that will generate the valid parenthesis.  

- return result  

// _generateParenthesis(current, n, left, right, result)  

- if right == n  
  - result.push_back(current) and return  
- else  
  - if left < n  
    - call _generateParenthesis(current + '(', n, left + 1, right, result)  

  - if left > right  
    - call _generateParenthesis(current + ')', n, left, right + 1, result)

C++ solution

class Solution {  
public:  
    void _generateParenthesis(string current, int n, int left, int right, vector<string>& result) {  
        if(right == n){  
            result.push_back(current);  
            return;  
        } else {  
            if(left < n){  
                _generateParenthesis(current + '(', n, left + 1, right, result);  
            }  

            if(left > right){  
                _generateParenthesis(current + ')', n, left, right + 1, result);  
            }  
        }  
    }  

    vector<string> generateParenthesis(int n) {  
        vector<string> result;  
        _generateParenthesis("", n, 0, 0, result);  

        return result;  
    }  
};

Golang solution

func generateParenthesis(n int) []string {  
    result := make([]string, 0)  

    _generateParenthesis("", n, 0, 0, &result)  
    return result  
}  

func _generateParenthesis(current string, n, left, right int, result *[]string) {  
    if right == n {  
        *result = append(*result, current)  
        return  
    } else {  
        if left < n {  
            _generateParenthesis(current + "(", n, left + 1, right, result)  
        }  

        if left > right {  
            _generateParenthesis(current + ")", n, left, right + 1, result)  
        }  
    }  
}

Javascript solution

var generateParenthesis = function(n) {  
    let result = [];  

    _generateParenthesis("", n, 0, 0, result);  

    return result;  
};  

var _generateParenthesis = function(current, n, left, right, result){  
    if( right === n ) {  
        result.push(current);  
        return;  
    } else {  
        if( left < n ) {  
           _generateParenthesis(current + '(', n, left + 1, right, result);  
        }  

        if( left > right) {  
            _generateParenthesis(current + ')', n, left, right + 1, result);  
        }  
    }  
}

Let’s dry-run our algorithm to see how the solution works.

Input: n = 2  

Step 1: vector<string> result;  

Step 2: _generateParenthesis("", n, 0, 0, result)  

// in _generateParenthesis(current, n, left, right, result)  

Step 3: right == n  
        0 == 2  
        false  

        left < n  
        0 < 2  
        true  

        _generateParenthesis(current + '(', n, left + 1, right, result)  
        _generateParenthesis('' + '(', 2, 0 + 1, 0, [])  
        _generateParenthesis('(', 2, 1, 0, [])  

Step 4: right == n  
        0 == 2  
        false  

        left < n  
        1 < 2  
        true  

        _generateParenthesis(current + '(', n, left + 1, right, result)  
        _generateParenthesis('(' + '(', 2, 1 + 1, 0, [])  
        _generateParenthesis('((', 2, 2, 0, [])  

Step 5: right == n  
        0 == 2  
        false  

        left < n  
        2 < 2  
        false  

        left > right  

        2 > 0  
        true  

        _generateParenthesis(current + ')', n, left, right + 1, result)  
        _generateParenthesis('((' + ')', 2, 2, 0 + 1, [])  
        _generateParenthesis('(()', 2, 2, 1, [])  

Step 6: right == n  
        1 == 2  
        false  

        left < n  
        2 < 2  
        false  

        left > right  

        2 > 1  
        true  

        _generateParenthesis(current + ')', n, left, right + 1, result)  
        _generateParenthesis('(()' + ')', 2, 2, 1 + 1, [])  
        _generateParenthesis('(())', 2, 2, 2, [])  

Step 7: right == n  
        2 == 2  
        true  

        result.push_back(current)  
        [].push_back("(())")  
        ["(())"]  

Step 8: This step goes to the next line of Step 4, where the left is set to 1 and the right is 0.  

        left = 1  
        right = 0  
        current = '('  

        _generateParenthesis(current + ')', n, left, right + 1, result)  
        _generateParenthesis('(' + ')', 2, 1, 0 + 1, ["(())"])  
        _generateParenthesis('()', 2, 1, 1, ["(())"])  

Step 9: right == n  
        1 == 2  
        false  

        left < n  
        1 < 2  
        true  

        _generateParenthesis(current + '(', n, left + 1, right, result)  
        _generateParenthesis('()' + '(', 2, 1 + 1, 1, ["(())"])  
        _generateParenthesis('()(', 2, 2, 1, ["(())"])  

Step 10: right == n  
         1 == 2  
         false  

         left < n  
         2 < 2  
         false  

         left > right  
         2 > 1  

         _generateParenthesis(current + ')', n, left, right + 1, result)  
         _generateParenthesis('()(' + ')', 2, 2, 1 + 1, ["(())"])  
         _generateParenthesis('()()', 2, 2, 2, ["(())"])  

Step 11: right == n  
         2 == 2  
         true  

         result.push_back(current)  
         ["(())"].push_back("()()")  

Control flows back to Step 3 and then fallbacks to Step 2.  

We return result as ["(())", "()()"].