无聊的刷题笔记

Generate Parentheses

LeetCode 22

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


class Solution {
public:
vector<string> ans;
void re(stack<char> charStack, int n, string parentheses){
if (n==0 && charStack.empty()) {
ans.push_back(parentheses);
}else {
if (!charStack.empty()) {
stack<char> tmpStack = charStack;
char tmp = tmpStack.top();
tmpStack.pop();
string tmpString = parentheses;
tmpString.append(1, tmp);
re(tmpStack, n, tmpString);
}
if (n!=0) {
string tmpString = parentheses;
stack<char> tmpStack = charStack;
tmpString.append("(");
tmpStack.push(')');
re(tmpStack, n-1, tmpString);
}
}
}
vector<string> generateParenthesis(int n) {
re(stack<char>(), n, string(""));
return ans;
}
};