LeetCode之括号生成问题

题目：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
原题的LeetCode链接：https://leetcode-cn.com/problems/generate-parentheses/

这道题有递归和动态规划两种思路，本文先讲解递归思路，DP思路过后补充。
有些题解说这可以看成深度优先or广度优先问题，我觉得这样想很牵强。树的构建和遍历包含着递归的思想，而不是递归的思想基于树，所以我还是觉得直接去想递归的思路最好，抓住本质。
我们可以通过递归的方式枚举出所有可能的排列，然后进行判断：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        generateAll(new char[2*n], 0, res);
        return res;
    }
    public void generateAll(char[] cur, int pos, List<String> res) {
        if(cur.length == pos) {
            if(valid(cur)) res.add(new String(cur));
        }
        else {
            cur[pos]='(';
            generateAll(cur,pos+1,res);
            cur[pos]=')';
            generateAll(cur,pos+1,res);
        }
    }
    public boolean valid(char[] cur) {
        int balance=0;
        for (char c : cur) {
            if(c=='(') balance++;
            else{
                balance--;
                if(balance<0) return false;
            }
        }
        return (balance==0);
    }
}

这种方法的时间复杂度为 $o\left ( 2^{n}*n \right )$o(2n∗n) 通过剪枝操作，可以降低是时间复杂度。
剪枝操作的方法叫做回溯法，在人工智能课程里被列为单独的一个章节，有兴趣的同学可以自己去看。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        generate(new StringBuffer(), 0, 0, n, res);
        return res;
    }
    public void generate(StringBuffer cur, int left, int right, int max, List<String> res) {
        if(cur.length() == 2*max) {
            res.add(cur.toString());//转换成String类型
        }
        else {
            if(left<max) {
                cur.append('(');
                generate(cur,left+1,right, max, res);
                cur.deleteCharAt(cur.length()-1);
            }
            if(right<left) {
                cur.append(')');
                generate(cur,left,right+1, max, res);
                cur.deleteCharAt(cur.length()-1);
            }
        }
    }
}

此时时间复杂度大大降低，具体的计算方法是一个卡特兰数，感兴趣的同学可以算算看。