LC22 General Parentheses 回溯/递归 生产所有有效的括号对
程序员文章站
2024-01-04 11:15:15
...
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
LeetCode括号系列之一,难度一般,很直接的想到使用回溯。
回溯从左往右生成一个新的组合的时候,判断条件是通过判断left和right两个指标。举例说明,numbers of pairs, which is n, equals to 3,其中left表示剩下的可用的做括号数;同理right表示剩余的右括号数。观察从左往右生成新组合的过程,什么情况下当前组合是valid?答案是:只要left小于等于right都是有效的,其中当left==right==0时说明已经没有括号剩余,当前组合可以加入到给目标数组。这道题只要意识到上面的observation就没有任何难度了。代码如下:
void getParanthesis(vector<string>& ans, string curr, int left, int right) {
//left: number of remaining '('
//right: number of remaining ')'
if (left > right) {
return;
}
if (left == 0 && right == 0) {
ans.push_back(curr);
}
else {
if (left > 0) {
getParanthesis(ans, curr + "(", left - 1, right);
}
if(right > 0) {
getParanthesis(ans, curr + ")", left, right -1);
}
}
}
vector<string> generateParenthesis(int n) {
vector<string> ans;
getParanthesis(ans, "", n, n);
return ans;
}