【Leetcode 热题 100】22. 括号生成

问题背景

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

• $1\le n\le 8$

解题过程

这题有一个不是很明显的需要理解的点，处理的过程中是先搞定左括号，再解决右括号的。
在这个前提下，生成的字符串是不可能出现括号不匹配（同一组括号先开再闭）的情况的，只要严格约束两种括号的数量，其它都可以交给递归来完成。

具体实现

选左括号还是右括号（不选左括号）

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] path = new char[2 * n];
        dfs(0, 0, n, path, res);
        return res;
    }

    private void dfs(int i, int leftCount, int n, char[] path, List<String> res) {
        // 递归边界是产生的字符串达到符合要求的长度
        if(i == 2 * n) {
            res.add(new String(path));
            return;
        }
        // 如果左括号的数量尚未达到要求，那就再填一个并进一步递归
        if(leftCount < n) {
            path[i] = '(';
            dfs(i + 1, leftCount + 1, n, path, res);
        }
        // 如果右括号的数量小于左括号的数量，那就在当前位置上覆盖一个右括号，并进一步递归
        if(i - leftCount < leftCount) {
            path[i] = ')';
            dfs(i + 1, leftCount, n, path, res);
        }
    }
}

选择在哪一个位置上填左括号

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, 0, n, path, res);
        return res;
    }

    // i 表示当前已经填入的括号总数，diff 表示左括号比右括号多的数量
    private void dfs(int i, int diff, int n, List<Integer> path, List<String> res) {
        // 递归边界是产生的字符串达到符合要求的长度，在相应的位置上填上左括号并生成答案
        if(path.size() == n) {
            char[] chS = new char[2 * n];
            Arrays.fill(chS, ')');
            for(int item : path) {
                chS[item] = '(';
            }
            res.add(new String(chS));
            return;
        }
        // 枚举合理的右括号的数量
        for(int rightCount = 0; rightCount <= diff; rightCount++) {
            // 从已经完成匹配的右括号开始尝试，找出合理的左括号的位置
            path.add(i + rightCount);
            // 这一轮操作尝试填入了 1 个左括号，rightCount 个右括号
            dfs(i + rightCount + 1, diff - rightCount + 1, n, path, res);
            path.remove(path.size() - 1);
        }
    }
}