今日算法之_32_括号生成
前言
Github:https://github.com/HealerJean
1、括号生成
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
示例1:
例如,给出 n = 3,生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
1.1、解题思路
首先明白一定要让括号成立,我们不妨从头开始向下走一遍 ,发现两个条件,如下:
生出左节点的条件:只要剩余左括号数量大于0就可以
生成右节点的条件:左括号的剩余数量必须大于剩余右括号的数量(你就想,如果右括号比左括号多了,能合上吗,亲)
1.2、算法
1.2.1、算法1 ,深度优先遍历,从后往前
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
//一对括号也没有,返回空集合
if (n == 0) {
return res;
}
// 执行深度优先遍历,搜索可能的结果
dfs("", n, n, res);
return res;
}
/**
* @param curStr 当前递归得到的结果
* @param left 左括号还有几个可以使用
* @param right 右括号还有几个可以使用
* @param res 结果集
*/
private void dfs(String curStr, int left, int right, List<String> res) {
// 在递归终止的时候,直接把它添加到结果集即可,
if (left == 0 && right == 0) {
res.add(curStr);
return;
}
// 剪枝(如图,左括号可以使用的个数严格大于右括号可以使用的个数,才剪枝,注意这个细节)
if (left > right) {
return;
}
//如果左节点或者右节点大于 0 ,则添加即可
if (left > 0) {
dfs(curStr + "(", left - 1, right, res);
}
if (right > 0) {
dfs(curStr + ")", left, right - 1, res);
}
}
1.2.2、算法2 ,深度优先遍历,从前往后
// 做减法
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
//一对括号也没有,返回空集合
if (n == 0) {
return res;
}
// 执行深度优先遍历,搜索可能的结果
dfs("", 0, 0, n, res);
return res;
}
/**
*
* @param curStr 当前递归得到的结果
* @param left 左括号当前使用了几个
* @param right 右括号当前使用了几个
* @param n 总共有多少个
* @param res 结果集
*/
private void dfs(String curStr, int left, int right,int n, List<String> res) {
// 构建数完成,直接把它添加到结果集即可,
if (left == n && right == n) {
res.add(curStr);
return;
}
// 剪枝(如图,左括号可以使用的个数严格大于右括号可以使用的个数,才剪枝,注意这个细节)
// if ( (n-left) > (n - right) ) {
if (right > left) {
return;
}
//如果左节点或者右节点大于 0 ,则添加即可
if (left <= n) {
dfs(curStr + "(", left + 1, right, n ,res);
}
if (right <= n) {
dfs(curStr + ")", left, right + 1, n, res);
}
}
1.3、测试
@Test
public void test(){
System.out.println(generateParenthesis(2));
}