友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
-
1 <= n <= 8
思路分析
使用回溯法解题时，需要关注的一个点是，在递归调用时，为了保证结果是有效的括号对，则添加的闭区间符号不能多于开区间符号。也就是，保证添加在添加一个闭区间符号之前，要先添加了对应的开区间符号。所以，就要注意闭区间的判断，是跟开区间大小判断，而不是括号数量。并不是所有的排列组合都符合我们的需求。
也可以去掉回溯过程，使用深度优先遍历。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Runtime: 2 ms, faster than 21.88% of Java online submissions for Generate Parentheses.
*
* Memory Usage: 45.3 MB, less than 5.16% of Java online submissions for Generate Parentheses.
*
* Copy from: https://leetcode.com/problems/generate-parentheses/solution/[Generate Parentheses solution - LeetCode]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2019-07-27 08:11
*/
public List<String> generateParenthesis(int n) {
List<String> ans = new LinkedList<>();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> result, String curr, int open, int close, int n) {
if (curr.length() == 2 * n) {
result.add(curr);
return;
}
if (open < n) {
backtrack(result, curr + "(", open + 1, close, n);
}
if (close < open) {
backtrack(result, curr + ")", open, close + 1, n);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-16 23:23:48
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
StringBuilder path = new StringBuilder(n * 2);
backtrack(n, n, result, path);
return result;
}
private void backtrack(int left, int right,
List<String> result, StringBuilder path) {
if (left == 0 && right == 0) {
result.add(path.toString());
return;
}
// left < 0 表示已经添加了超量的左括号
// left > right 表示右括号数量大于左括号
if (left < 0 || left > right) {
return;
}
char[] chars = {'(', ')'};
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
path.append(c);
if (i == 0) {
backtrack(left - 1, right, result, path);
} else {
backtrack(left, right - 1, result, path);
}
path.deleteCharAt(path.length() - 1);
}
}