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:

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

Solution: Backtracking

Let's only add bracket when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

We use l to represent the number of opening brackets, and r to represent the number of closing brackets.

    void backtrack(vector<string> &ans, string str, int open, int close, int n) {
        if (str.size() == 2*n) {
            ans.push_back(str);
            return;
        }

        if (open < n) backtrack(ans, str+"(", open+1, close, n);
        if (close < open) backtrack(ans, str+")", open, close+1, n);
    }

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

Solution:

vector<string> generateParenthesis(int n) {
    if (n == 0) return {""};

    vector<string> ans;
    for (int i = 0; i<n; i++) {
        for (auto left: generateParenthesis(i)) {
            for (auto right: generateParenthesis(n-1-i)) {
                ans.push_back("(" + left + ")" + right);
            }
        }
    }
    return ans;
}