22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

思路

回溯先画树：

image.png

递归出口：
符合结果：当(的剩余个数==)的剩余个数==0时，得到一个解
剪枝条件：当)的剩余个数 多于 (的剩余个数，是不符合要求的解，需要剪枝掉

代码

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循环，后来看了答案，发现多余的
//        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);
//            }
//        }

    }
}