22、Generate Parentheses

题设

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

要点

• 回溯 backtracking
• 剪枝

明显地，可以用回溯法来解。判断条件为：

    leftCount:左括号数
    rightCount：右括号数
    str: 记录生成的括号串

    leftCount > n => 不可能有解，剪枝
    rightCount > leftCount => 不可能有解，剪枝
    str.length() == n * 2：得到一个解

回溯法在每一步，本来应该用for循环，枚举此次所有可能的情况，如八皇后的棋盘列数。但是这里只有加左括号和右括号两种，直接写就可以了。

代码：

    public List<String> generateParenthesis(int n){
        List<String> list = new ArrayList<String>();
        if(n == 0)
            return list;

        backTrack(list , n , 0 , 0 , "");
        return list;
    }

    /*
        leftCount:左括号数
        rightCount：右括号数
        str: 记录生成的括号串

        leftCount > n => 不可能有解，剪枝
        rightCount > leftCount => 不可能有解，剪枝
        str.length() == n * 2：得到一个解
     */
    public void backTrack(List<String> list , int n , int leftCount , int rightCount , String str){
        // 剪枝
        if(leftCount > n)
            return;
        if(rightCount > leftCount)
            return;

        // 找到正确答案
        if(str.length() == n * 2){
            list.add(str);
            return;
        }

        // 这里本来应该用for循环，枚举此次所有可能的情况，如八皇后的棋盘列数。但是这里只有加左括号和右括号两种，直接写就可以了
        // 左括号的情况
        str += '(';
        int newLeftCount = leftCount + 1;
        backTrack(list , n , newLeftCount , rightCount , str);

        // 回溯
        str = str.substring(0 , str.length() - 1);

        // 右括号的情况
        str += ')';
        if(str.length() == 1)// 第一位不可能是')'
            return;
        int newRightCount = rightCount + 1;
        backTrack(list , n , leftCount , newRightCount , str);

    }