LeetCode_22_括号生成

1.题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

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

2.思路分析

如果是对n个字符排列，总共有多少种排序方法？一共有n！种。
那现在问题变了，字符只有两种'(' 和 ')'，并且我们要考虑到，要满足括号的合理性。两次剪枝。
用树来枚举所有的可能：

树组织方式

DFS:
①总共有n个左括号和n个右括号
②当左括号小于n的时候可以继续添加：(
③当右括号使用数小于左括号的时候，可以添加：)
结束条件：没有右括号可以使用了

3.代码实现

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

    public static void getParenthesis(String cur,int n, List<String> list, int left, int right) {
        if(right==n){
            list.add(cur);
            return;
        }

        if(left<right)return;

        if(left>right){
            getParenthesis(cur+")",n,list,left,right+1);
        }
        if(left<n){
            getParenthesis(cur+"(",n,list,left+1,right);
        }
    }