leetcode 22. Generate Parentheses
题意
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:
”((()))”, “(()())”, “(())()”, “()(())”, “()()()”
分析
- 二叉树递归
代码(递归解法)
class Solution {
public:
vector<string> generateParenthesis(int n) {
if(n == 0){
return vector<string>();
}
vector<string> res;
dfs(res, "",n,n);
return res;
}
void dfs(vector<string> &res,string tmp,int left,int right){
if(left == 0 && right ==0){
res.push_back(tmp);
return;
}
if(right > left){
dfs(res,tmp+")",left,right-1);
}
if(right >= left && left > 0){
dfs(res,tmp+"(",left-1,right);
}
}
};
