DFS + 回溯法解决字符串生成问题

22.题目链接-来源:力扣(LeetCode)

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

示例 1:

输入:n = 3
输出:[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

思路:

这是字符串生成的问题,可以考虑 DFS + 回溯法。
我们利用 DFS 递归地遍历当前下一位所有可能的括号组合(当前至多有 2 种选择),然后用回溯法回到递归前的状态,当左右括号数等于所需的对数时,即收集结果。如此我们可以遍历每一位的括号组合。
细节:「剪枝」,即进行下一步之前,通过条件判断过滤掉一些不可能的选择,比如,右括号不能多于左括号,所以当左右括号数相等时,我们下一步只能添加左括号;否则,我们既可以添加左括号,也可右括号,依次回溯遍历即可。
时间复杂度:O(4^n/n^0.5)
空间复杂度:O(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
36
class Solution {
public List<String> generateParenthesis(int n) {
int l = 0, r = 0;
sb = new StringBuilder();
ret = new LinkedList<>();
helper(l, r, n);
return ret;
}
private StringBuilder sb;
private List<String> ret;
private void helper(int l, int r, int n) {
if (l > r && l < n) {
for (int i = 0; i < 2; i++) {
if (i == 0) {
sb.append('(');
helper(l + 1, r, n);
sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(')');
helper(l, r + 1, n);
sb.deleteCharAt(sb.length() - 1);
}
}
} else if (l == r && l < n) {
sb.append('(');
helper(l + 1, r, n);
sb.deleteCharAt(sb.length() - 1);
} else {
for (int i = 0; i < n - r; i++) {
sb.append(')');
}
ret.add(sb.toString());
sb.delete(sb.length() - n + r, sb.length());
}
}
}