LeetCode22.括号生成

题目描述

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

思路分析

1. 生成括号，可以 使用深度优先+剪枝的方式，将有效的组合保存到集合中，将无效的组合剪枝
2. 编写一个深度优先的递归函数，实现不断的拼接字符串，即不断的向初始的空字符串拼接左括号或者右括号
3. 函数中给定的n值即为左括号也为右括号的个数，在拼接过程中，当发现左括号个数和右括号个数都为0时，说明找到一个满足的括号组合，将其加入集合中
4. 因为满足条件的字符串组合中。左括号总在在右括号的前面，即剩余的右括号的个数大于等于左括号的个数，否则说明有右括号匹配不到左括号，不满足条件
5. 当上述条件都不满足时，说明括号还没拼接成功，先向左括号递归，然后再向右括号递归
6. 源码见下

源码及分析

public List<String> generateParenthesis(int n) {
        String cur = "";
        List<String> list = new ArrayList<>();
        dfs(cur, n, n, list);
        return list;
    }
    /**
     * 深度优先
     *
     * @param cur   当前递归得到的结果
     * @param left  左括号还有几个
     * @param right 右括号还有几个
     * @param res   结果
     */
    public void dfs(String cur, int left, int right, List<String> res) {
        //如果递归到左右括号都使用完并且满足条件则添加到结果集
        if (left == 0 && right == 0) {
            res.add(cur);
            return;
        }
        //剪枝，因为有效的括号总是先左侧再右侧，因此剩余的括号中左侧总是小于等于右侧，
        // 一旦出现右侧括号小于左侧括号数的情况，说明这种情况无效
        if (left > right) {
            return;
        }
        //先递归左括号
        if (left > 0) {
            dfs(cur + "(", left - 1, right, res);
        }
        //再递归右括号
        if (right > 0) {
            dfs(cur + ")", left, right - 1, res);
        }
    }

LeetCode22.括号生成