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:
"((()))", "(()())", "(())()", "()(())", "()()()"
思路：产生所有合理的括号配对
我自己用的回溯法，遍历所有压入第k个')'时前面'('个数
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
if(n == )
return ans;
vector<vector<char>> S(n); //放入第k个右括号时，已经放入的左括号数目
int k = ;
for(int i = k + ; i <= n; i++)
{
S[k].push_back(i);
}
string X;
while(k >= )
{
while(!S[k].empty())
{
int numOfLeftP = getNumOfLeft(X); //还没有放入的左括号数目
while(numOfLeftP < S[k].back()) //如果X中"("少于需要的，压入"("
{
X.append("(");
numOfLeftP++;
}
while(numOfLeftP > S[k].back()) //如果X中"("多于需要的，弹出
{
char back = X.back();
X.pop_back();
if(back == '(')
{
numOfLeftP--;
}
}
X.append(")"); //压入新的")"
int back = S[k].back();
S[k].pop_back();
if(k < n - )
{
k++;
int num = max(back, k + ); //可以选择的已有左括号数必须大于当前已有的 小于等于n
for(int i = num; i <= n; i++)
{
S[k].push_back(i);
}
}
else
{
ans.push_back(X);
}
}
k--;
}
return ans;
}
int getNumOfLeft(string X)
{
int position=;
int i=;
while((position=X.find_first_of("(",position))!=string::npos)
{
position++;
i++;
}
return i;
}
};
我的思路很繁琐，中间要做各种判断，看下大神的。
产生长度为 2*n的括号， 但是不能随便产生
设len是当前的字符串长度， v是当前完整配对的括号对数
如果 len - v < n 还可以放入'('
如果 2 * v < len 还可以放入')'
当长度符合条件就压入答案，只有这时stack长度才会减小，其他长度下会压入新值。
vector<string> generateParenthesis2(int n) {
vector<string> ans;
vector<string> stack;
vector<int> validationStack;
stack.push_back("(");
validationStack.push_back();
while(stack.size() != )
{
string s = stack.back();
stack.pop_back();
int v = validationStack.back();
validationStack.pop_back();
if(s.length() == * n)
{
ans.push_back(s);
continue;
}
if(s.length() - v < n)
{
stack.push_back(s.append("("));
validationStack.push_back(v);
s.pop_back();
}
if( * v < s.length())
{
stack.push_back(s.append(")"));
validationStack.push_back(v + );
s.pop_back();
}
}
return ans;
}