给定括号对数量，输出所有可能组合
如果给你一个题目，“给出一个正整数，表示一共有多少对括号，如何输出所有括号可能的组合？”，你会如何做呢？
例如：给出的括号对数为3， 则所有括号的组合有如下几种：
()()()
()(())
(())()
(()())
((()))针对该问题，本文我将为大家给出两种解决方法：
- 广度优先搜索的方式
- 深度优先搜索的方式
方法一：广度优先搜索
1.1 思想
所谓广度优先搜索的方式就是尽可能早的先输出完整的括号对(), 也就是当输出一个左括号 '(' ， 尽可能先输出一个右括号 ‘)’ 。
比如：要输出括号对数是2对的所有可能，先输出的结果是()(), 而不是(())。
()()
(())我们可以定义三个值来完成递归调用：
currParentheses 当前存放的括号组合情况
leftCount 剩余左括号数
rightCount 剩余右括号数1.2 什么时候输出一个候选结果？
当剩余左括号数和剩余右括号数都为0的时候。
1.3 左括号'('和右括号'')输出的时机？
广度优先搜索的目的是先得到完整的括号对(), 这种情况下需要需要考虑如下两种情况：
- 输出右边括号')'的时机：如果剩余的右括号数大于剩余的左括号数，那么意味着之前已经有一个左括号输出了，在这种情况下，将当前存放的括号组合情况添加一个右括号，然后剩余右边括号数减1，然后继续递归调用。
- 输出左边括号'('的时机：如果剩余的左括号数leftCount大于0，则当前存放的括号组合情况添加一个左括号'(', 然后剩余左括号数减1，然后继续递归调用。
有了上述的思想，我们可以很容易写出相应的程序来。具体代码如下：
/**
* 广度优先搜索递归函数
* @param currParentheses 当前存放的括号组合情况
* @param leftCount 剩余左括号数
* @param rightCount 剩余右括号数
*/
private void bfsRecu(String currParentheses, int leftCount, int rightCount) {
/**
* 结束条件：
* 当剩余括号数和剩余右括号数都为0时，表示括号已经用完，直接输出就可以打印出一种情况
*/
if (leftCount == 0 && rightCount == 0) {
System.out.println(currParentheses);
}
/**
* 广度优先搜索的目的是先得到完整的括号对(), 这种情况下
* 需要检查剩余的右括号数是否大于剩余的左括号数，如果大于则表示已经有一个左括号输出了，
* 在这种情况下，将当前存放的括号组合情况添加一个右括号，然后右边括号数减1，然后递归调用
*
*/
if (rightCount > leftCount) {
bfsRecu(currParentheses + ')', leftCount, rightCount - 1);
}
/**
* 如果还有剩余左括号数，则将当前存放的括号组合情况添加一个左括号，然后剩余左边括号数减1，然后递归调用即可
*/
if (leftCount > 0) {
bfsRecu(currParentheses + '(', leftCount - 1, rightCount);
}
}有了广度优先搜索的递归调用函数，广度优先搜索方法就可以调用递归函数即可。当前存放括号内容的变量为空。
/**
* 广度搜索方式打印括号组合数字
* @param parentheseCount 括号对数
*/
public void bfs(int parentheseCount) {
if (parentheseCount < 1) {
throw new IllegalArgumentException("括号对数不能小于1");
}
bfsRecu("", parentheseCount, parentheseCount);
}方法二：深度优先搜索
2.1 思想
深度优先搜索的思路和广度优先搜索类似，唯一的区别就是先输出完整的括号对，还是先尽可能多地输出左括号。
广度优先搜索的方式就是尽可能早的先输出完整的括号对(), 也就是当输出一个左括号 '(' ， 尽可能先输出一个右括号 ‘)’ 。
深度优先搜索的方式就是尽可能早的先输出左括号('', 也就是如果剩余左括号数大于0的时，先获取左边括号'('。
比如要输出括号对数是2对的所有可能，先输出的结果是(()), 而不是()()。
(())
()()和广度优先搜索一样，我们依旧可以定义三个值来完成递归调用：
currParentheses 当前存放的括号组合情况
leftCount 剩余左括号数
rightCount 剩余右括号数2.2 什么时候输出一个候选结果？
当剩余左括号数和剩余右括号数都为0的时候。
2.3 左括号'('和右括号'')输出的时机？
深度优先搜索的目的是先尽可能多的得到左括号'(', 这种情况下需要需要考虑如下两种情况：
- 输出左边括号'('的时机：如果剩余的左括号数leftCount大于0，则当前存放的括号组合情况添加一个左括号'(', 然后剩余左括号数减1，然后继续递归调用。
- 输出右边括号')'的时机：如果剩余的右括号数大于剩余的左括号数，那么意味着之前已经有一个左括号输出了，在这种情况下，将当前存放的括号组合情况添加一个右括号，然后剩余右边括号数减1，然后继续递归调用。
有了上述的思想，我们可以很容易写出相应的程序来。具体代码如下：
/**
* 深度优先搜索递归方法
* @param currParentheses 当前存放的括号组合情况
* @param leftCount 剩余左括号数
* @param rightCount 剩余右括号数
*/
private void dfsRecu(String currParentheses, int leftCount, int rightCount) {
/**
* 结束条件：
* 当剩余括号数和剩余右括号数都为0时，表示括号已经用完，直接输出就可以打印出一种情况
*/
if (leftCount == 0 && rightCount == 0) {
System.out.println(currParentheses);
}
/**
* 深度优先搜索的目的是尽可能先获取左边括号, 这种情况下, 如果剩余左括号数大于0，则
* 将当前存放的括号组合情况添加一个左括号，然后剩余左边括号数减1，然后递归调用
*
*/
if (leftCount > 0) {
dfsRecu(currParentheses + '(', leftCount - 1, rightCount);
}
/**
* 检查剩余的右括号数是否大于剩余的左括号数，如果大于，
* 则将当前存放的括号组合情况添加一个右括号，然后右边括号数减1，然后递归调用
*
*/
if (rightCount > leftCount) {
dfsRecu(currParentheses + ')', leftCount, rightCount - 1);
}
}有了深度优先搜索的递归调用函数，深度优先搜索方法就可以调用递归函数即可。
/**
* 深度搜索方式打印括号组合数字
* @param parentheseCount 括号对数
*/
public void dfs(int parentheseCount) {
if (parentheseCount < 1) {
throw new IllegalArgumentException("括号对数不能小于1");
}
dfsRecu("", parentheseCount, parentheseCount);
}测试代码和测试结果
/**
* @author wangmengjun
*/
public class ParenthesesPrinter {
/**
* 广度搜索方式打印括号组合数字
* @param parentheseCount 括号对数
*/
public void bfs(int parentheseCount) {
if (parentheseCount < 1) {
throw new IllegalArgumentException("括号对数不能小于1");
}
bfsRecu("", parentheseCount, parentheseCount);
}
/**
* 广度优先搜索递归函数
* @param currParentheses 当前存放的括号组合情况
* @param leftCount 剩余左括号数
* @param rightCount 剩余右括号数
*/
private void bfsRecu(String currParentheses, int leftCount, int rightCount) {
/**
* 结束条件：
* 当剩余括号数和剩余右括号数都为0时，表示括号已经用完，直接输出就可以打印出一种情况
*/
if (leftCount == 0 && rightCount == 0) {
System.out.println(currParentheses);
}
/**
* 广度优先搜索的目的是先得到完整的括号对(), 这种情况下
* 需要检查剩余的右括号数是否大于剩余的左括号数，如果大于则表示已经有一个左括号输出了，
* 在这种情况下，将当前存放的括号组合情况添加一个右括号，然后右边括号数减1，然后递归调用
*
*/
if (rightCount > leftCount) {
bfsRecu(currParentheses + ')', leftCount, rightCount - 1);
}
/**
* 如果还有剩余左括号数，则将当前存放的括号组合情况添加一个左括号，然后剩余左边括号数减1，然后递归调用即可
*/
if (leftCount > 0) {
bfsRecu(currParentheses + '(', leftCount - 1, rightCount);
}
}
/**
* 深度搜索方式打印括号组合数字
* @param parentheseCount 括号对数
*/
public void dfs(int parentheseCount) {
if (parentheseCount < 1) {
throw new IllegalArgumentException("括号对数不能小于1");
}
dfsRecu("", parentheseCount, parentheseCount);
}
/**
* 深度优先搜索递归方法
* @param currParentheses 当前存放的括号组合情况
* @param leftCount 剩余左括号数
* @param rightCount 剩余右括号数
*/
private void dfsRecu(String currParentheses, int leftCount, int rightCount) {
/**
* 结束条件：
* 当剩余括号数和剩余右括号数都为0时，表示括号已经用完，直接输出就可以打印出一种情况
*/
if (leftCount == 0 && rightCount == 0) {
System.out.println(currParentheses);
}
/**
* 深度优先搜索的目的是尽可能先获取左边括号, 这种情况下, 如果剩余左括号数大于0，则
* 将当前存放的括号组合情况添加一个左括号，然后剩余左边括号数减1，然后递归调用
*
*/
if (leftCount > 0) {
dfsRecu(currParentheses + '(', leftCount - 1, rightCount);
}
/**
* 检查剩余的右括号数是否大于剩余的左括号数，如果大于，
* 则将当前存放的括号组合情况添加一个右括号，然后右边括号数减1，然后递归调用
*
*/
if (rightCount > leftCount) {
dfsRecu(currParentheses + ')', leftCount, rightCount - 1);
}
}
}/**
* @author wangmengjun
*
*/
public class Main {
public static void main(String[] args) {
ParenthesesPrinter example = new ParenthesesPrinter();
for (int i = 2; i <= 5; i++) {
System.out.println(String.format("广度优先搜索, %d对括号所有的可能组合,", i));
example.bfs(i);
System.out.println();
System.out.println(String.format("深度优先搜索, %d对括号所有的可能组合,", i));
example.dfs(i);
System.out.println();
}
}
}运行结果如下：
广度优先搜索, 2对括号所有的可能组合,
()()
(())
深度优先搜索, 2对括号所有的可能组合,
(())
()()
广度优先搜索, 3对括号所有的可能组合,
()()()
()(())
(())()
(()())
((()))
深度优先搜索, 3对括号所有的可能组合,
((()))
(()())
(())()
()(())
()()()
广度优先搜索, 4对括号所有的可能组合,
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))
深度优先搜索, 4对括号所有的可能组合,
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
广度优先搜索, 5对括号所有的可能组合,
()()()()()
()()()(())
()()(())()
()()(()())
()()((()))
()(())()()
()(())(())
()(()())()
()(()()())
()(()(()))
()((()))()
()((())())
()((()()))
()(((())))
(())()()()
(())()(())
(())(())()
(())(()())
(())((()))
(()())()()
(()())(())
(()()())()
(()()()())
(()()(()))
(()(()))()
(()(())())
(()(()()))
(()((())))
((()))()()
((()))(())
((())())()
((())()())
((())(()))
((()()))()
((()())())
((()()()))
((()(())))
(((())))()
(((()))())
(((())()))
(((()())))
((((()))))
深度优先搜索, 5对括号所有的可能组合,
((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()有兴趣的读者可以自己动手试试～
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读