Leetcode22：括号生成

题目

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

解法

  private static List<String> generate(int n) {
        List<String> dataList=new ArrayList<>();
        if (n==0)return dataList;
        dfs("",n,n,dataList);
        return dataList;
    }

• DFS做减法方式

  private static void dfs(String current, int left, int right, List<String> dataList) {
        // 递归结束添加到list中
        if (left==0&&right==0){
            dataList.add(current);
            return;
        }
        if (left>right){
            return;
        }

        if (left>0){
            dfs(current+"(",left-1,right,dataList);
        }
        if (right>0){
            dfs(current+")",left,right-1,dataList);
        }

    }

• DFS做加法方式

    private static void dfsIncrease(String current, int left, int right,int length, List<String> dataList) {
        // 递归结束添加到list中
        if (left==length&&right==length){
            dataList.add(current);
            return;
        }
        if (left<right){
            return;
        }

        if (left<length){
            dfsIncrease(current+"(",left+1,right,length,dataList);
        }
        if (right<length){
            dfsIncrease(current+")",left,right+1,length,dataList);
        }

    }

• 参考： https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/