(广度优先搜索)打印所有可能的括号组合

 

问题：给定一个正整n，作为括号的对数，输出所有括号可能的组合，如
n=2
(())
()()

n = 3的情况
((()))
(()())
(())()
()(())
()()()

在之前的一篇文章中，我们采用了深度优先搜索的方式实现：(深度优先搜索)打印所有可能的括号组合

本博文中，我们将给出采用广度优先搜索的方式实现，程序如下：

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/