22 Generate Parentheses

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

For example, given n= 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

The Idea: Recursive build from the base case where if n = 0, then sol = { "" }, and if n = 1, then sol = { "()" }. If we continue this pattern, we will notice that every nth case can be built from n-1th case. That is, for every nth case, we insert a parenthesis pair "()" to every left parenthesis. Additionally, we insert a parenthesis pair at the beginning. To take care of duplicates, use an unordered_set. One big problem with this implementation is that we end up calculating a lot of redundent parenthesis sets.

Complexity:

vector<int> find_left_paren_loc(const string &s) {
    vector<int> locs;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            locs.push_back(i);
    }
    return locs;
}

vector<string> _generateParenthesis(int n, vector<string> &prev, unordered_set<string> &unique) {
    if (n > 0) {
        vector<string> next;
        for (string &s : prev) {

            vector<string> candidates;
            vector<int> left_locs = find_left_paren_loc(s);
            for (int i : left_locs) {
                string str_cp = s;
                candidates.push_back(str_cp.insert(i + 1, "()"));
            }
            candidates.push_back("()" + s);

            for (const string &s1 : candidates) {
                if (unique.find(s1) == unique.end()) {
                    next.push_back(s1);
                    unique.insert(s1);
                }
            }
        }
        return _generateParenthesis(n - 1, next, unique);
    }

    return prev;
}

vector<string> generateParenthesis(int n) {
    unordered_set<string> unique;
    vector<string> prev;

    prev.push_back("");
    return _generateParenthesis(n, prev, unique);
}


int main() 
{
    for (int i : {0, 1, 2, 3, 4, 5, 6}) {
        print(generateParenthesis(i));
        cout << endl;
    }
}

Solution 2 with optimal time complexity:

Maintain two integers which will denote the number of remaining left and right parenthesis. Initially, we know that we need n left parenthesis and as a general rule, we can only have a right parenthesis if the current number of left parenthesis exceeds the number of right parenthesis. For example, if we have 0 left parenthesis, then there is no way we can have a right. However, when we have 2 left parenthesis - we can branch out with a right. So it follows that number of left parenthesis can only decrease, while the number or right parenthesis can only increase only when a left parenthesis is introduced.

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        solutions = []
        def __generateParenthesis(cur, left, right):
            if left == 0 and right == 0:
                solutions.append(cur)
            else:
                if right:
                    __generateParenthesis(cur + ')', left, right - 1)
                if left:
                    __generateParenthesis(cur + '(', left - 1, right + 1)

        __generateParenthesis('', n, 0)
        return solutions


obj = Solution()
print(obj.generateParenthesis(4))