输出指定括号对数的所有可能组合

如果给出一个正整数，表示一共有多少对括号，如何输出所有括号可能的组合？

比如：给出的括号对数为3， 则所有括号的组合有如下几种：

为了解决这个问题，本文采用两种方式来完成。

• 广度优先搜索的方式
• 深度优先搜索的方式

接下来，我们一起来看看广度优先搜索和深度优先搜索的思想和具体实现。

广度优先搜索方式

思想

所谓广度优先搜索的方式就是尽可能早的先输出完整的括号对(), 也就是当输出一个左括号 '(' ， 尽可能先输出一个右括号 ‘)’ 。

比如要输出括号对数是2对的所有可能，先输出的结果是()(), 而不是(())。

我们可以定义三个值来完成递归调用：

什么时候输出一个候选结果？

当剩余左括号数和剩余右括号数都为0的时候。

左括号'('和右括号'')输出的时机？

广度优先搜索的目的是先得到完整的括号对(), 这种情况下需要需要考虑如下两种情况：

• 输出右边括号')'的时机：如果剩余的右括号数大于剩余的左括号数，那么意味着之前已经有一个左括号输出了，在这种情况下，将当前存放的括号组合情况添加一个右括号，然后剩余右边括号数减1，然后继续递归调用。
• 输出左边括号'('的时机：如果剩余的左括号数leftCount大于0，则当前存放的括号组合情况添加一个左括号'(', 然后剩余左括号数减1，然后继续递归调用。

有了上述的思想，我们可以很容易写出相应的程序来。具体代码如下：

代码实现

有了广度优先搜索的递归调用函数，广度优先搜索方法就可以调用递归函数即可。当前存放括号内容的变量为空。

深度优先搜索方式

思想

深度优先搜索的思路和广度优先搜索类似，唯一的区别就是先输出完整的括号对，还是先尽可能多地输出左括号。

广度优先搜索的方式就是尽可能早的先输出完整的括号对(), 也就是当输出一个左括号 '(' ， 尽可能先输出一个右括号 ‘)’ 。 深度优先搜索的方式就是尽可能早的先输出左括号('', 也就是如果剩余左括号数大于0的时，先获取左边括号'('。

比如要输出括号对数是2对的所有可能，先输出的结果是(()), 而不是()()。

和广度优先搜索一样，我们依旧可以定义三个值来完成递归调用：

什么时候输出一个候选结果？

当剩余左括号数和剩余右括号数都为0的时候。

左括号'('和右括号'')输出的时机？

深度优先搜索的目的是先尽可能多的得到左括号'(', 这种情况下需要需要考虑如下两种情况：

• 输出左边括号'('的时机：如果剩余的左括号数leftCount大于0，则当前存放的括号组合情况添加一个左括号'(', 然后剩余左括号数减1，然后继续递归调用。
• 输出右边括号')'的时机：如果剩余的右括号数大于剩余的左括号数，那么意味着之前已经有一个左括号输出了，在这种情况下，将当前存放的括号组合情况添加一个右括号，然后剩余右边括号数减1，然后继续递归调用。

有了上述的思想，我们可以很容易写出相应的程序来。具体代码如下：

代码实现

有了深度优先搜索的递归调用函数，深度优先搜索方法就可以调用递归函数即可。

完整代码和测试结果

完整代码

测试代码和结果

运行结果如下：