Leetcode Guide: Generate Parenthesis Problem Solution

Question Description:

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

Examples:

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 8

Asked By:

• 

  Facebook

• 

  Amazon

• 

  Microsoft

• 

  Apple

• 

  Adobe

(Note: This information has not been confirmed.)

Solution:

This problem requires us to generate valid parentheses combinations given a variable n that represents the number of pairs of parentheses.

The intuitive approach that comes to mind reading this problem is recursion. With this approach in mind, we need to devise an algorithm that generates all valid parentheses combinations while avoiding invalid patterns (e.g., a pair like ")(").

To solve this problem, we need variables to track the number of opening and closing parentheses used out of the total number given. Let's name these variables f and b, respectively.

To avoid invalid parentheses conditions, we will ensure that the value of f is always less than that of b, as we want our pattern to always start with an opening parenthesis and end with a closing parenthesis.

• Keeping this in mind, we will start our pattern with an opening parenthesis, setting f = 2 and b = 3 (for example, when n = 3).

• We then have two options: either use one more f or use b. When we use f, the condition remains the same, but when we use b, we only have one option, which is to use f, as using b would lead to an invalid pattern. Therefore, we can establish a condition that f < b, and if b > f, we need to return to the previous function state.

Looking at the recursive tree should give you a proper understanding of the working of the algorithm.

Code (JS, Python, C++, Java):

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let list = [];
    rec("", n, n, list);
    return list;
};

function rec(s, f, b, list) {
    if (b < f) {
        return;
    }
    if (f === 0 && b === 0) {
        list.push(s);
        return;
    }
    if (f > 0) {
        rec(s + "(", f - 1, b, list);
    }
    if (b > 0) {
        rec(s + ")", f, b - 1, list);
    }
}

class Solution:
    def __init__(self):
        self.list = []

    def generateParenthesis(self, n):
        self.rec("", n, n)
        return self.list

    def rec(self, s, f, b):
        if b < f:
            return
        if f == 0 and b == 0:
            self.list.append(s)
            return
        if f > 0:
            self.rec(s + "(", f - 1, b)
        if b > 0:
            if f < b:
                self.rec(s + ")", f, b - 1)

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> list;
        rec("", n, n, list);
        return list;
    }

private:
    void rec(string s, int f, int b, vector<string>& list) {
        if (b < f) {
            return;
        }
        if (f == 0 && b == 0) {
            list.push_back(s);
            return;
        }
        if (f > 0) {
            rec(s + "(", f - 1, b, list);
        }
        if (b > 0) {
            if (f < b) {
                rec(s + ")", f, b - 1, list);
            }
        }
    }
};

class Solution {
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        rec("", n, n);
        return list;
    }

    private void rec(String s, int f, int b) {
        if (b < f) {
            return;
        }
        if (f == 0 && b == 0) {
            list.add(s);
            return;
        }
        if (f > 0) {
            rec(s + "(", f - 1, b);
        }
        if (b > 0) {
            if (f < b) {
                rec(s + ")", f, b - 1);
            }
        }
    }
}