括号生成
程序员文章站
2024-03-21 17:32:58
...
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
使用深度优先搜索算法(DFS),递归操作。对于结果,我们只需要关心左右括号数量一致等于n,而且我们需要保证左右括号数量相等,也就是当左右括号数量不一致的时候,立即在小于n的时候,添加对应的括号。请看代码注释:
public class GenerateParenthesis {
//使用深度优先搜索算法,也是递归算法,最终的结果就是左右括号的数量都是n个
//如果左边不够n个左括号,先填满它先
//然后,左括号的数量肯定就是大于右边括号数量了,这个时候继续增加右边括号
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
int leftCount = 0;//左括号数量
int rightCount = 0;//右边括号数量
String tmpSubResult = "";//临时结果集
dfs(leftCount, rightCount, tmpSubResult, result, n);
return result;
}
public void dfs(int left, int right, String tmpSubResult, List<String> result, int n) {
if (left == n && right == n) {//如果左右括号数量都是n,那就是结果集了
result.add(tmpSubResult);
return;
}
//递归过程中,如果left还小于n,继续增加左括号
if (left < n) {
dfs(left + 1, right, tmpSubResult + "(", result, n);
}
//如果发现左括号数量大于右括号了,马上增加一个右括号
if (left > right) {
dfs(left, right + 1, tmpSubResult + ")", result, n);
}
}
}