题目地址

https://leetcode-cn.com/problems/generate-parentheses/

题目描述

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

示例：

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

题解

暴力枚举

class Solution {
    public List<String> generateParenthesis(int n) {
        // 一个括号有 2 个符号
        // 所以一共有 2 * n 个符号

        // 1. 枚举所有的状态，一共 2^(2*n) 个
        List<String> allStates = new ArrayList<>();
        allStates.add("");
        int length = 2 * n;
        for (int i = 0; i < length; ++ i) {
            allStates = buildNext(allStates);
        }

        // 2. 把正确的状态，加入到结果中
        List<String> results = new ArrayList<>();
        for (int i = 0; i < allStates.size(); ++ i) {
            String state = allStates.get(i);
            if (isCorrect(state)) {
                results.add(state);
            }
        }
        return results;
    }

    public List<String> buildNext(List<String> prevs) {
        List<String> nexts = new ArrayList<>();
        for (int i = 0; i < prevs.size(); ++ i) {
            String prev = prevs.get(i);
            nexts.add(prev + "(");
            nexts.add(prev + ")");
        }
        return nexts;
    }

    public boolean isCorrect(String str) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); ++ i) {
            char letter = str.charAt(i);
            if (letter == '(') {
                stack.push(letter);
            } else {
                if (stack.size() == 0) {
                    return false;
                }
                stack.pop();
            }
        }

        // 栈空表示括号都匹配上了
        return stack.size() == 0;
    }
}

时间复杂度 O(2^n)，n 为传入的参数。

耗时有点长，但是通过了，说明时间复杂度是符合题意的。

还能怎么优化呢？

通过观察，我们可以发现一个符号条件的【括号组合】，其任一前缀都含有一个规律，那就是： sum(left bracket) >= sum(right bracket)。
因此，如果有一个前置状态的 sum(left bracket) < sum(right bracket) 那么就可以进行剪枝，不再继续枚举后续的状态。

dfs（回溯算法）

不需要枚举所有的状态，不符合条件的状态提前进行剪枝。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<>();
        dfs(n, n, "", results);
        return results;
    }

    public void dfs(int remainLeftBracketNum,int remainRightBracketNum, String brackets, List<String> results) {
        // 小于 0，表示超出范围
        if (remainLeftBracketNum < 0 || remainRightBracketNum < 0) {
            return;
        }
        // 剩余的左括号比右括号多，说明已经存在的左括号比右括号少
        if (remainLeftBracketNum > remainRightBracketNum) {
            return;
        }

        // 符合条件
        if (remainLeftBracketNum == 0 && remainRightBracketNum == 0) {
            results.add(brackets);
            return;
        }



        // 1. 追加一个左括号
        dfs(remainLeftBracketNum - 1, remainRightBracketNum, brackets + "(", results);
        
        // 回溯
        // 因为 Java 中 String 是不可变对象，brackets + "(" 会返回一个新的 String 对象，不会改变原有的 brackets
        // 因此这里可以不处理

        // 2. 追加一个右括号
        dfs(remainLeftBracketNum, remainRightBracketNum - 1, brackets + ")", results);
    }
}

时间复杂度 O(2^n)，n 为传入的参数。

可以看到，通过剪枝，执行时间大大减少。