ChoDocs

外观

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