?
问题:给定一个正整n,作为括号的对数,输出所有括号可能的组合,如 n=2 (()) ()() n = 3的情况 ((())) (()()) (())() ()(()) ()()()
在之前的一篇文章中,我们采用了深度优先搜索的方式实现:(深度优先搜索)打印所有可能的括号组合
本博文中,我们将给出采用广度优先搜索的方式实现,程序如下:
class="java" name="code">public class ParenthesesGenerator { public void generateParentheses(int parenthesesCount) { bfs("", parenthesesCount, parenthesesCount); } /** * 采用深度搜索优先的方式 BFS(breadth-first search) * * @param currentParentheses * @param remanentLeftParenthesesRemain * @param remanentRightParenthesesRemain */ private void bfs(String currentParentheses, int remanentLeftParenthesesRemain, int remanentRightParenthesesRemain) { /** * 如果左括号数和右括号数都为0的时候,表示已经找到一种解决方式, 直接输出结果 */ if (remanentLeftParenthesesRemain == 0 && remanentRightParenthesesRemain == 0) { System.out.println(currentParentheses); } /** * 如果右括号剩余数大于左括号剩余数,则添加一个右括号,右括号剩余数减去1,然后递归调用自身 */ if (remanentRightParenthesesRemain > remanentLeftParenthesesRemain) { bfs(currentParentheses + ")", remanentLeftParenthesesRemain, remanentRightParenthesesRemain - 1); } /** * 如果左括号数还有剩余,则将当前括号组成字符添加一个左括号, 然后递归调用本身 */ if (remanentLeftParenthesesRemain > 0) { bfs(currentParentheses + "(", remanentLeftParenthesesRemain - 1, remanentRightParenthesesRemain); } } }
?
测试程序及其结果如下
public class ParenthesesGeneratorTest { public static void main(String[] args) { ParenthesesGenerator test = new ParenthesesGenerator(); for (int i = 1; i < 5; i++) { System.out.printf("有%d括号的所有组合:\n", i); test.generateParentheses(i); } } }
?
有1括号的所有组合: () 有2括号的所有组合: ()() (()) 有3括号的所有组合: ()()() ()(()) (())() (()()) ((())) 有4括号的所有组合: ()()()() ()()(()) ()(())() ()(()()) ()((())) (())()() (())(()) (()())() (()()()) (()(())) ((()))() ((())())
原文地址 http://thecodesample.com/?p=954
更多代码实例请访问 http://thecodesample.com/