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

Java基础

浏览数:91

2020-5-30

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

比如:给出的括号对数为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对括号所有的可能组合,
((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()

 

作者:王孟君