如果给出一个正整数，表示一共有多少对括号，如何输出所有括号可能的组合？
比如：给出的括号对数为3， 则所有括号的组合有如下几种：
()()() ()(()) (())() (()()) ((()))
为了解决这个问题，本文采用两种方式来完成。
- 广度优先搜索的方式
- 深度优先搜索的方式
接下来，我们一起来看看广度优先搜索和深度优先搜索的思想和具体实现。
广度优先搜索方式
思想
所谓广度优先搜索的方式就是尽可能早的先输出完整的括号对(), 也就是当输出一个左括号 ‘(‘ ， 尽可能先输出一个右括号 ‘)’ 。
比如要输出括号对数是2对的所有可能，先输出的结果是()(), 而不是(())。
()() (())
我们可以定义三个值来完成递归调用：
currParentheses 当前存放的括号组合情况 leftCount 剩余左括号数 rightCount 剩余右括号数
什么时候输出一个候选结果？
当剩余左括号数和剩余右括号数都为0的时候。
左括号'(‘和右括号”)输出的时机？
广度优先搜索的目的是先得到完整的括号对(), 这种情况下需要需要考虑如下两种情况：
- 输出右边括号‘)’的时机：如果剩余的右括号数大于剩余的左括号数，那么意味着之前已经有一个左括号输出了，在这种情况下，将当前存放的括号组合情况添加一个右括号，然后剩余右边括号数减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);
}
深度优先搜索方式
思想
深度优先搜索的思路和广度优先搜索类似，唯一的区别就是先输出完整的括号对，还是先尽可能多地输出左括号。
广度优先搜索的方式就是尽可能早的先输出完整的括号对(), 也就是当输出一个左括号 ‘(‘ ， 尽可能先输出一个右括号 ‘)’ 。
深度优先搜索的方式就是尽可能早的先输出左括号(”, 也就是如果剩余左括号数大于0的时，先获取左边括号'(‘。
比如要输出括号对数是2对的所有可能，先输出的结果是(()), 而不是()()。
(()) ()()
和广度优先搜索一样，我们依旧可以定义三个值来完成递归调用：
currParentheses 当前存放的括号组合情况 leftCount 剩余左括号数 rightCount 剩余右括号数
什么时候输出一个候选结果？
当剩余左括号数和剩余右括号数都为0的时候。
左括号'(‘和右括号”)输出的时机？
深度优先搜索的目的是先尽可能多的得到左括号'(‘, 这种情况下需要需要考虑如下两种情况：
- 输出左边括号‘(‘的时机：如果剩余的左括号数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对括号所有的可能组合, ((((())))) (((()()))) (((())())) (((()))()) (((())))() ((()(()))) ((()()())) ((()())()) ((()()))() ((())(())) ((())()()) ((())())() ((()))(()) ((()))()() (()((()))) (()(()())) (()(())()) (()(()))() (()()(())) (()()()()) (()()())() (()())(()) (()())()() (())((())) (())(()()) (())(())() (())()(()) (())()()() ()(((()))) ()((()())) ()((())()) ()((()))() ()(()(())) ()(()()()) ()(()())() ()(())(()) ()(())()() ()()((())) ()()(()()) ()()(())() ()()()(()) ()()()()()
原文地址：https://my.oschina.net/wangmengjun/blog/760138
