22. 括號生成

數(shù)字 n 代表生成括號的對數(shù)，請你設計一個函數(shù)，用于能夠生成所有可能的并且 有效的 括號組合。
示例 1：
輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
輸入：n = 1
輸出：["()"]

思路

回溯先畫樹：

image.png

遞歸出口：
符合結果：當(的剩余個數(shù)==)的剩余個數(shù)==0時，得到一個解
剪枝條件：當)的剩余個數(shù) 多于 (的剩余個數(shù)，是不符合要求的解，需要剪枝掉

代碼

class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        dfs("", n, n, res);
        return res;
    }

    private void dfs(String s, int leftLeft, int rightLeft, List<String> res) {
        if (rightLeft < leftLeft) {
            return;
        }
        if (rightLeft == 0 && leftLeft == 0) {
            res.add(s);
            return;
        }
//剛開始寫時候是嚴格按照回溯方法寫的，所以有個for循環(huán)，后來看了答案，發(fā)現(xiàn)多余的
//        for (int i = 0; i<2; i++){
//            if (i == 0){
                if (leftLeft > 0) {
                    dfs(s + "(", leftLeft - 1 , rightLeft, res);
                }
//            }
//            else {
        if (rightLeft > 0)
                dfs(s + ")", leftLeft, rightLeft - 1 , res);
//            }
//        }

    }
}