欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}

相关标签: 算法题

上一篇:

下一篇: