22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
1
2
3
4
5
6
7
8
| Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
|
C++ Solution
```c++
class Solution {
public:
bool isValid(string s) {
stack parentheses;
for (auto character : s) {
switch (character) {
case '(':
case '[':
case '{':
parentheses.push(character);
break;
case ')':
if (parentheses.empty() || parentheses.top() != '(') {
return false;
}
if (!parentheses.empty()) {
parentheses.pop();
}
break;
case ']':
if (parentheses.empty() || parentheses.top() != '[') {
return false;
}
if (!parentheses.empty()) {
parentheses.pop();
}
break;
case '}':
if (parentheses.empty() || parentheses.top() != '{') {
return false;
}
if (!parentheses.empty()) {
parentheses.pop();
}
break;
}
}
return parentheses.empty();
}
vector generateParenthesis(int n) {
vector result{""};
vector parenthesis{"(", ")"};
for (int i = 0; i < n * 2; i++) {
vector newResult;
for (auto str : result) {
for (auto symbol : parenthesis) {
newResult.push_back(str + symbol);
}
}
result = newResult;
}
vector validResult;
for (auto item : result) {
if (isValid(item)) {
validResult.push_back(item);
}
}
return validResult;
}
};
`
