LeetCode 22 括号生成
题目:
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
题解:
经典DFS算法
根据 LC20_IsValid 我们定义的有效括号的特性可得到以下规律:
1.我们必须保证每次放入后，右括号数必须小于或者等于左括号，即每个右括号一定要能匹配一个左括号
2.如果一个括号组放入的左括号组的数量等于我们定义的括号对数量，则只能放入右括号
3.其他情况即可以放入左括号，也可以放入右括号
图解:
图解
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
dfs(list, 0, n, new StringBuilder());
return list;
}
private void dfs(List<String> list, int put, int remain, StringBuilder s) {
if (put == 0 && remain == 0) {
list.add(s.toString());
} else if (put == 0 && remain > 0) {
dfs(list, put + 1, remain - 1, s .append('('));
} else if (put > 0 && remain == 0) {
dfs(list, put - 1, remain, s.append(')'));
} else {
dfs(list, put + 1, remain - 1, new StringBuilder(s.toString()).append('('));
dfs(list, put - 1, remain, new StringBuilder(s).append(')'));
}
}
|