题目

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

示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

思路-回溯暴力版

回溯穷举所有括号的组合，检测如果括号是有效的就加入结果。
每次检测括号的有效性花费O(n)，效率很低：

17 ms, 在所有 Java 提交中击败了5.51%的用户

代码

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backtrack(n, new StringBuilder());
        return res;
    }
    public void backtrack(int n, StringBuilder path) {
        if (path.length() == n*2) {
            if (valid(path)) {
                res.add(path.toString());
            }
            return;
        }
        path.append("(");
        backtrack(n, path);
        path.deleteCharAt(path.length() - 1);
        path.append(")");
        backtrack(n, path);
        path.deleteCharAt(path.length() - 1);
    }
    public boolean valid(StringBuilder sb) {
        Stack<Character> stack = new Stack<>();
        for (char c : sb.toString().toCharArray()) {
            if (c == '(') {
                stack.add(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

思路-回溯优化版

在回溯树中每次做选择的时候，看分别还有多少左括号和右括号剩余。如果剩余的左括号数量大于右括号，说明生成的括号字符串是无效的。

backtrack(..., int left_count, int right_count)
left_count: 在树中的某一个节点上，这一时刻剩余的左括号的数量
right_count: 在树中的某一个节点上，这一时刻剩余的右括号的数量

代码

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backtrack(n, new StringBuilder(), n, n);
        return res;
    }

    public void backtrack(int n, StringBuilder path, int left_count, int right_count) {
        if (left_count > right_count) {
            return;
        }
        if (left_count == 0 && right_count == 0) {
            res.add(path.toString());
            return;
        }

        if (left_count > 0) {  // 左分支
            path.append("(");
            backtrack(n, path, left_count - 1, right_count);
            path.deleteCharAt(path.length() - 1);
        }
        if (right_count > 0) { // 右分支
            path.append(")");
            backtrack(n, path, left_count, right_count - 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}