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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Seen this question in a real interview before? Yes
No
思路:递归法,两个限制条件:
1,左括号和右括号的数量都为0的时候
2,只有当左括号<右括号的数量时才能添加右括号上去,否则无效
AC代码:
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
generate("",n,n,result);
return result;
}
private:
void generate(string item,int left,int right,vector<string> &result){
if(left==0&&right==0){
result.push_back(item);
return;
}
if(left>0){
generate(item+'(',left-1,right,result);
}
if(left<right){
generate(item+')',left,right-1,result);
}
}
};
网友评论