LeetCode-in-All
22. Generate Parentheses
Medium
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Constraints:
1 <= n <= 8
Solution
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string current;
generate(current, ans, n, n);
return ans;
}
private:
void generate(string& current, vector<string>& ans, int open, int close) {
if (open == 0 && close == 0) {
ans.push_back(current);
return;
}
if (open > 0) {
current.push_back('(');
generate(current, ans, open - 1, close);
current.pop_back();
}
if (close > 0 && open < close) {
current.push_back(')');
generate(current, ans, open, close - 1);
current.pop_back();
}
}
};