Leetcode-22. 括号生成

难度中等2135

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

思路

运用二叉树dfs加剪枝算法

image-20211107162639000

首先运用二叉树将所有情况排列出来，我们发现有很多是不符合要求的，我们现在运用剪枝算法将不符合要求的剪掉。

`public List<String> generateParenthesis(int n) {`
    `List<String> res = new ArrayList<>();`
    `if (n <= 0) return res;`
    `dfs(n, "", res);`
    `return res;`
`}`

`private void dfs(int n, String path, List<String> res) {`
    `if (path.length() == 2 * n) {`
        `res.add(path);`
        `return;`
    `}`

```java
dfs(n, path + "(", res);
dfs(n, path + ")", res);
```

`}`

剪枝算法

我们首先定义左括号的个数为op，右括号的个数为cl，首先op的个数不能大于n，又因为括号是闭合的，所以在排列的过程中右括号的个数要小于左括号的个数，除此之外，排列不能用右括号开始。

image-20211107164030983

void dfs(int n, String path, List<String> res, int open, int close) {
    if (open > n || close > open) return;

```java
if (path.length() == 2 * n) {
    res.add(path);
    return;
}

dfs(n, path + "(", res, open + 1, close);
dfs(n, path + ")", res, open, close + 1);
```

}

代码：

`class Solution {`

  `public List<String> generateParenthesis(int n) {`

​    `List<String> res =new ArrayList<>();`

​    `if(n<=0) return res;`

​    `dfs(n,"",res,0,0);`

​    `return res;`

  `}`

  `private void dfs(int n,String path,List<String> res,int open,int close){`

​    `if(open>n||close>open) return;`

​    `if(path.length()==2*n){`

​      `res.add(path);`

​      `return;`

​    `}`

​    `dfs(n,path+"(",res,open+1,close);`

​    `dfs(n,path+")",res,open,close+1);`

  `}`

`}`
Last modification：November 7th, 2021 at 04:44 pm
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏