Generate Parentheses

Posted by Bill on March 30, 2023

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; } }; `