https://leetcode.com/problems/generate-parentheses/description/
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
中文翻譯:
給你N個左括號，N個右括號，請你列出所有合理的組合(如上例)。
[Solution]
Recursively choosing parentheses under previous condition.
Main operation of recursive function:
There are 2N slots for you to put left or right parenthesis in.
In each round, you can choose either a left or a right parenthesis,
and leave the rest of the parentheses to the following recursive function call.
Recursive function terminates when :
1.No parenthesis left.
2.Number of left parentheses is more than number of right parentheses.
Let's write code~
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ret;
string ans;
gen(n,n,ans,ret);
return ret;
}
void gen(int l, int r, string& ans, vector<string>& ret){
if(l>r) return;
if(l==r && l==0){
ret.push_back(ans);
return;
}
if(l>0){
ans.push_back('(');
gen(l-1,r,ans,ret);
ans.pop_back();
}
if(r>0){
ans.push_back(')');
gen(l,r-1,ans,ret);
ans.pop_back();
}
}
};
