22. 括号生成

难度中等

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

示例：

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

回溯法

public 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 s,int left,int right,List<String> res){
        if(left==0&&right==0){
            res.add(s);
            return;
        }
        if(right<left)
            return;
        if(left>0)
            dfs(s+'(',left-1,right,res);
        if(right>0)
            dfs(s+')',left,right-1,res);

    }
}

LeetCode 第 22 题：“括号生出”题解配图.png

这种回溯问题要首先画树图找出关键信息，在此题中，就是左括号数量严格大于右括号数量时，剪枝 这一限制条件，从而确保生成的括号字符串正确

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/