Skip to content

LeetCode 22. 括号生成 中等

作者:Choi Yang
更新于:6 个月前
字数统计:646 字
阅读时长:2 分钟
阅读量:

题目描述

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

javascript
输入:n = 3
输出:[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

示例 2:

javascript
输入:n = 1
输出:["()"]

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

这道题,看了大佬的题解,发现真是有意思,现在来解释一下。

我们可以直接走可行的情况,对于不可行的情况,自然就剪掉了。

关键在于左右括号如何选择,首先,对于左括号,起初我们必然是要选的,然后我们也可以全部选完,因此,只要有左括号我们必须选,而对于右括号而言,它的剩余数量必须大于剩余左括号数量,我们才能选右括号。

举个反例,假如我们现在已经有了 (())n = 3,然后左右括号都还剩一个,如果理解选 ),岂不是就 (()))了,显示不是有效的括号,应该被剪掉才是,因此,我们必须严格右括号剩余数量必须大于剩余左括号数量,我们才能选右括号。

参考 笨猪爆破组 大佬图解

javascript
var generateParenthesis = function (n) {
  let res = [];
  let dfs = (cur, left, right) => {
    if (cur.length === 2 * n) {
      res.push(cur);
      return;
    }
    // 左括号还存在,就可以选左括号
    if (left > 0) dfs(cur + "(", left - 1, right);
    // 右括号数量要大于左括号,才可以选右括号
    if (right > left) dfs(cur + ")", left, right - 1);
  };
  dfs("", n, n);
  return res;
};
cpp
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs("", n, n, res);
        return res;
    }
    void dfs(string cur, int left, int right, vector<string>& res) {
        if (left == 0 && right == 0) {
            res.push_back(cur);
            return;
        }
        if (left > 0) dfs(cur + "(", left - 1, right, res);
        if (right > left) dfs(cur + ")", left, right - 1, res);
    }
};
java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs("", n, n, res);
        return res;
    }
    void dfs(String cur, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(cur);
            return;
        }
        if (left > 0) dfs(cur + "(", left - 1, right, res);
        if (right > left) dfs(cur + ")", left, right - 1, res);
    }
}
python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(cur, left, right):
            if left == 0 and right == 0:
                res.append(cur)
                return
            if left > 0: dfs(cur + "(", left - 1, right)
            if right > left: dfs(cur + ")", left, right - 1)
        dfs("", n, n)
        return res
javascript
学如逆水行舟,不进则退

Contributors

Choi Yang