Question ：

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:



"((()))", "(()())", "(())()", "()(())", "()()()"



Anwser 1 ：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> vec;
        string str;
        addParen(vec,str, n, n);

        return vec; 
    }
    
    void addParen(vector<string> &vec, string str, int left, int right) {        
        if (left == 0 && right == 0) {
            vec.push_back(str);
            return;
        }

        if (left > 0) {
            addParen(vec, str + '(', left - 1, right);
        }

        if (right > left) {
            addParen(vec, str + ')', left, right-1);
        }        
    }
};

Anwser 2 ：

class Solution {
public:
    void printPar(int l, int r, vector<string>& result, char* str, int idx)
    {
        if (l < 0 || r < l) return;
        if (l == 0 && r == 0)
        {
            str[idx] = '';
            result.push_back(string(str));
        }
        else
        {
            if (l > 0)
            {
                str[idx] = '(';
                printPar(l-1, r, result, str, idx+1);
            }
            if (r > l)
            {
                str[idx] = ')';
                printPar(l, r-1, result, str, idx+1);
            }
        }
    }
    
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> result;
        char* str = new char[2*n+1];
        printPar(n, n, result, str, 0);
        delete []str;
        return result;
    }
};

Anwser 3 ：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> ans;
        if (n > 0) {
            generator(ans, "", 0, 0, n);
        }
        return ans;
    }
    
    // r/l: appearance of ) (
    void generator(vector<string> & ans, string s, int l, int r, int n) { 
        if (l == n) {
            ans.push_back(s.append(n-r, ')'));
            return;
        }
        generator(ans, s + '(', l+1, r, n);
        if (l > r) {
            generator(ans, s + ")", l, r+1, n);
        }
    }
};

参考推荐：

Generate Parentheses

LeetCode: Generate Parentheses