括号生成 - 简书

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

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

image.png

画图以后，可以分析出的结论：

1.当前左右括号都有大于 00 个可以使用的时候，才产生分支；

2.产生左分支的时候，只看当前是否还有左括号可以使用；

3.产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；

4.在左边和右边剩余的括号数都等于 00 的时候结算。

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

Java代码：

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

    public void dfs(String cur_str, int left, int right, List<String> res) {
        //因为每一次尝试，都使用新的字符串变量，所以不需要回溯
        //在递归终止的时候，直接将其添加到结果集中
        if(left == 0 && right == 0) {
            res.add(cur_str);
            return;
        }   
        
        //剪枝（左括号可以使用的个数严格大于右括号可以使用的个数才进行剪枝操作）
        if(left > right) return;

        if(left > 0) dfs(cur_str + '(', left - 1, right, res);
        if(right > 0) dfs(cur_str + ')',left, right - 1,res); 
    }
}