友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
22. Generate Parentheses
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:
[
"",
")(",
"))()", "()((",
"()()()"
]
解题分析
使用回溯法解题时，需要关注的一个点是，在递归调用时，为了保证结果是有效的括号对，则添加的闭区间符号不能多于开区间符号。也就是，保证添加在添加一个闭区间符号之前，要先添加了对应的开区间符号。所以，就要注意闭区间的判断，是跟开区间大小判断，而不是括号数量。并不是所有的排列组合都符合我们的需求。
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
/**
* 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]
*/
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);
}
}