21
04/2015
[LeetCode] Generate Parentheses
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题思路：
我第一感觉就是回溯，通过递归实现。但是递归的条件迟迟没有想出。可以这么做，分别记录当前字符串的（和）个数，若（个数小于n，当前字符串加上（，递归调用下一层。若）小于（的个数，当前字符加上），递归调用下一层。若（和）的数目都等于n，停止递归调用，将s加入结果集。代码如下：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
if(n<1){
return result;
}
getParenthesis(n, 0, 0, "", result);
return result;
}
void getParenthesis(int n, int leftNumber, int rightNumber, string s, vector<string>& result){
if(leftNumber==n&&rightNumber==n){
result.push_back(s);
return;
}
if(leftNumber<n){
getParenthesis(n, leftNumber+1, rightNumber, s+"(", result);
}
if(rightNumber<leftNumber){
getParenthesis(n, leftNumber, rightNumber+1, s+")", result);
}
}
};二次刷题（2015-08-18）
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
helper("", 0, 0, n, result);
return result;
}
void helper(string item, int left, int right, int n, vector<string>& result){
if(left == n && right == n){
if(item!=""){
result.push_back(item);
}
return;
}
if(left < n){
helper(item + "(", left + 1, right, n, result);
}
if(right < left){
helper(item + ")", left, right + 1, n, result);
}
}
};转载请注明：康瑞部落 » [LeetCode] Generate Parentheses
0 条评论