Leetcode#22 Generate parentheses
Published:
Link:
https://leetcode.com/problems/generate-parentheses/description/
Idea:
As long as number of left parenthesis >= number of right parenthesis, insert left or right. Otherwise, insert left ( only. When both counters reach limit, return result. Use Recursive function.
Solution:
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
int n_left = 0;
int n_right = 0;
string s = "";
help_func(n_left, n_right, n, s, res);
return res;
}
void help_func(int left, int right, int n, string &s, vector<string> &res) {
if (left == n && right == n){
res.push_back(s);
return;
}
if (left < n) {
s.push_back('(');
help_func(left+1, right, n, s, res);
s.pop_back();
}
if (right < left) {
s.push_back(')');
help_func(left, right+1, n, s, res);
s.pop_back();
}
}
};