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:
"((()))", "(()())", "(())()",
"()(())", "()()()"
思路：这是一道DFS题。规则是：在任意0-i的地方，"("的个数必须>=")"的个数才符合规则。因此，当left<n时，可使用"("，当left>right可使用")"。
class Solution {
private:
vector<string> res;
string perRes;
public:
void generateParenthesisHelper(int pos, int left, int right, int n) {
if (pos == 2*n) {
res.push_back(perRes);
}
else {
if (left < n) {
perRes[pos] = '(';
generateParenthesisHelper(pos+1, left+1, right, n);
}
if (left > right) {
perRes[pos] = ')';
generateParenthesisHelper(pos+1, left, right+1, n);
}
}
}
vector<string> generateParenthesis(int n) {
res.clear();
if(n <= 0) {
return res;
}
perRes.clear();
perRes.resize(2*n);
generateParenthesisHelper(0,0,0,n);
return res;
}
};