参考：
第7课-泛型递归、树的递归

LeetCode-22. 括号生成

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

image.png

1 不考虑括号的合法性

首先不考虑括号的合法性，可以将n对括号理解成 2*n个格子，每个格子中放入一个括号，可以使用递归实现。
按照第7课-泛型递归、树的递归中介绍的递归模板来实现。

递归模板共分为4个步骤：

1. 递归终止条件recursion terminator
2. 处理当前层process logic in current level
3. 下探到下一层drill down
4. 清理当前层reverse the current level status if need

java代码如下：

    public List<String> generateParenthesis(int n) {
        generate(0, 2 * n, "");
        return null;
    }

    public void generate(int level, int max, String s) {
        //递归终止条件
        //recursion terminator
        if (level > max) {
            System.out.println(s);
            return;
        }
        // 处理当前层
        //process logic in current level
        String s1 = s + "(";
        String s2 = s + ")";
        //下探到下一层
        //drill down
        generate(level + 1, max, s1);
        generate(level + 1, max, s2);
        //清理当前层
        //reverse the current level status if need
    }

此时打印出了所有括号的组合，此时当然也包括不合法的括号组合。

---

2 增加括号合法性判断

1. left == n && right == n 时，递归终止
2. 下探到下一层时先做括号合法性判断

    public List<String> generateParenthesis(int n) {
        generate(0, 0, n, "");
        return null;
    }

    public void generate(int left, int right, int n, String s) {
        //1 递归终止条件 recursion terminator
        if (left == n && right == n) {
            System.out.println(s);
            return;
        }
        //2 处理当前层 process logic in current level
        String s1 = s + "(";
        String s2 = s + ")";
        //3 下探到下一层 drill down
        if (left < n) {
            generate(left + 1, right, n, s1);
        }
//        if(left > right && right < n){//right < left,left < n,则right < n 一定成立。
        if (left > right) {
            generate(left, right + 1, n, s2);
        }
        //4 清理当前层reverse the current level status if need
    }

打印结果如下：

image.png

也可以将 处理当前层 合并到 下探下一层 中

    public void generate(int left, int right, int n, String s) {
        //1 递归终止条件 recursion terminator
        if (left == n && right == n) {
            System.out.println(s);
            return;
        }
        //2 处理当前层 process logic in current level
//        String s1 = s + "(";
//        String s2 = s + ")";
        //3 下探到下一层 drill down
        if (left < n) {
            generate(left + 1, right, n, s + "(");
        }
//        if(left > right && right < n){//right < left,left < n,则right < n 一定成立。
        if (left > right) {
            generate(left, right + 1, n, s + ")");
        }
        //4 清理当前层reverse the current level status if need
    }

---

最后按照题目要求使用List保存结果

    public static void main(String[] args) {
        S02_generate_parentheses sol = new S02_generate_parentheses();
        List<String> result = sol.generateParenthesis(3);
        System.out.println(result.toString());
    }

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

    public void generate(int left, int right, int n, String s) {
        //1 递归终止条件 recursion terminator
        if (left == n && right == n) {
            result.add(s);
//            System.out.println(s);
            return;
        }
        //2 处理当前层 process logic in current level
//        String s1 = s + "(";
//        String s2 = s + ")";
        //3 下探到下一层 drill down
        if (left < n) {
            generate(left + 1, right, n, s + "(");
        }
//        if(left > right && right < n){//right < left,left < n,则right < n 一定成立。
        if (left > right) {
            generate(left, right + 1, n, s + ")");
        }
        //4 清理当前层reverse the current level status if need
    }