LeetCode 22.括号生成

原题链接：. - 力扣（LeetCode）

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

思路：

本题可以采用 回溯的方法解决。将剩余可放置的 左括号 '('  数量 left 和 右括号 ')' 数量 right 作为参数传入 backtrack 函数中。

终止条件有三类：

• 一是 right < left，剩余可放置的 左括号的数量 大于 剩余可放置的右括号数量，则最后的组合必然不合法的，比如，剩余可以放置的 左括号数量为 3 )))，右括号数量为 2 ((，那么显然不能组成合法的括号对。
• 二是 left<0 || right<0，可放置数量小于0 是不合法的。
• 三是 left ==0 && right ==0，这种情况则合法，将 合法的字符串添加进 结果集中。

代码：

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n==0)return res;
        backtrack(n,n);
        return res;
    }
    StringBuilder path = new StringBuilder();
    //左括号还能放置的个数为left，右括号还能放置的个数为right
    public void backtrack(int left,int right){
        //如果左括号还能放置的个数多于右括号，则不合法
        if(right<left)return;
        //如果小于0，则不合法
        if(left<0||right<0)return;
        //如果left和right同时为0，则找到了一个合法的组合
        if(left==0&&right==0){
            res.add(path.toString());
        }

        //插入一个左括号试试
        path.append('(');
        backtrack(left-1,right);
        path.deleteCharAt(path.length()-1);

        //插入一个右括号试试
        path.append(')');
        backtrack(left,right-1);
        path.deleteCharAt(path.length()-1);
    }
}