0022. Generate Parentheses.md

22. Generate Parentheses, medium

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:

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

class Solution {
    void gen(vector<string>& res, string s, int n, int left, int right) {
        if (left == 0 && right == 0) {
            res.push_back(s);
            return;
        }
        int idx = 2*n - left - right;
        if (left > 0) {
            s[idx] = '(';
            gen(res, s, n, left - 1, right);
        }
        if (right > left) {
            s[idx] = ')';
            gen(res, s, n, left, right - 1);
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string s(2*n, ' ');
        gen(res, s, n, n, n);
        return res;
    }
};

class Solution {
public:
    void genPair(int i, int nl, int nr, string& str, vector<string>& vs) {
        if( nl == 0 && nr == 0) {
            vs.push_back(str);
            return;
        }
        if (nl > 0) {
            str[i] = '(';
            genPair(i+1, nl-1, nr, str, vs);
        }
        if (nr > nl) {
            str[i] = ')';
            genPair(i+1, nl, nr-1, str, vs);
        }
    }
    vector<string> generateParenthesis(int n) {
        string s(n*2, ' ');
        vector<string> vs;
        genPair(0, n, n, s, vs);
        return vs;
    }
};