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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Hide Tags
Backtracking String
Hide Similar Problems
(M) Letter Combinations of a Phone Number (E) Valid Parentheses
虽然跟电话键盘那题相似,但还是有些不同的:
第一个只能是左括号;
左括号的数量始终要比右括号多;
如果左右括号各剩一个,那就到头了,只能多加一个 "()";
如果左括号剩余零个,也到头了,只能把剩下的右括号全加上;
其他情况就可以左右都选,进行组合。
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> rst;
string buf="";
if(n)
{
buf += '('; build(n-1, n, buf, rst);
}
return rst;
}
void build(int ln, int rn, string& buf, vector<string>& rst)
{
//ending part I: only one possibility: add "()" if(1==ln && 1==rn)
rst.push_back(buf + "()");
//ending part II: all '(' are used, can only finish with all ')' else if(0==ln)
{
string tmp="";
while(rn)
tmp += ')', rn--;
rst.push_back(buf+tmp);
}
//between first and ending part else
{
//cannot put more ')' than all existing '(' if(ln<=rn) {
//try add '(' and move further if(ln)
{
buf.push_back('(');
build(ln-1, rn, buf, rst);
buf.pop_back();
}
//try add ')' and move further if(rn)
{
buf.push_back(')');
build(ln, rn-1, buf, rst);
buf.pop_back();
}
}
}
return;
}
};
0 ms.
这个写得挺简练:左边小于总数就可以加左边,右边小于左边就可以加右边。
No comments:
Post a Comment