括号生成

2020-12-10

22. 括号生成

难度中等1762

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

示例 1：

1 2	输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1 2	输入：n = 1 输出：["()"]

提示：

1 <= n <= 8

回溯方法

如果左括号的数量还没有满足,先生成左括号
如果右括号的数量小于左括号的数量就生成右括号,否则不生成右括号

class Solution {
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0,0,n*2);
        return list;
    }
    int n=0;
    List<String> list = new ArrayList<>();
    StringBuilder bd = new StringBuilder();
    public void dfs(int left,int right,int rest){
        if(rest==0){
            String s=bd.toString();
            list.add(s);
            return;
        }
        // 如果左括号的数量还没有满足,先生成左括号
        if(left<n){
            bd.append("(");
            dfs(left+1,right,rest-1);
            bd.deleteCharAt(bd.length()-1);
        }
        // 如果右括号的数量小于左括号的数量就生成右括号,否则不生成右括号
        if(left>right){
            bd.append(")");
            dfs(left,right+1,rest-1);
            bd.deleteCharAt(bd.length()-1);
        }
    }
}

暴力回溯

class Solution{
   List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        char[] seq = new char[2 * n];

        backtrack(seq, 0, 2 * n);

        return result;
    }

    public void backtrack(char[] seq, int cur, int max) {
        if (cur == max) {
            if (isValid(seq)) {
                result.add(new String(seq));
            }
        } else {
            seq[cur] = '(';
            backtrack(seq, cur + 1, max);
            seq[cur] = ')';
            backtrack(seq, cur + 1, max);
        }
    }


    public boolean isValid(char[] seq) {
        int balance = 0;
        for (char c : seq) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }
}

优化的回溯

//如果左括号的数量小于n，可以继续添加左括号
//如果右括号的数量小于左括号，可以继续添加右括号
这样就可以不用验证生成序列的正确性了

class Solution{
    List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        char[] seq = new char[2 * n];
        backtrack(seq, 0, 2 * n);
        return result;
    }
    //如果左括号的数量小于n，可以继续添加左括号
    //如果右括号的数量小于左括号，可以继续添加右括号
    public static void backtrack(StringBuilder bd, int cur, int max, int left, int right) {
        if (cur == max) {
            result.add(bd.toString());
        } else {
            if (left < max / 2) {
                bd.append('(');
                backtrack(bd, cur + 1, max, left + 1, right);
                bd.deleteCharAt(bd.length() - 1);
            }
            if (right < left) {
                bd.append(')');
                backtrack(bd, cur + 1, max, left, right + 1);
                bd.deleteCharAt(bd.length() - 1);
            }


        }

    }
}

按括号序列的长度递归


class Solution {
    ArrayList[] cache = new ArrayList[100];

    public List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c) {
                for (String left: generate(c)) {
                    for (String right: generate(n - 1 - c)) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }

    public List<String> generateParenthesis(int n) {
        return generate(n);
    }
}

参考文献


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。