22. 括号生成（回溯算法）

22. 括号生成

• 题目
• 解题思路
• 代码

题目

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

解题思路

这题套用回溯算法的模板就可以了。但是有两个注意的点就是回溯的结束条件。

代码

/*
本题之所以不用LinkedList等做路径，是因为会产生逗号，用字符串拼接的话就不会产生逗号
*/
class Solution {
    List<String> res = new LinkedList<>();

    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return res;
        }

        backtrack(n, n, "");
        return res;
    }

    /*left、right可用的左、右括号数量 str为路径*/
    public void backtrack(int left, int right, String str) {
        //一些结束条件
        if (left < 0 || right < 0) {
            return;
        }
        //剩下的左括号多余右括号，不合法。证明生成的括号中左括号少于右括号
        if (left > right) {
            return;
        }
        //左右括刚好用完，组成了合法的括号。不合法的情况在上两个if已经剔除了
        if (left == 0 && right == 0) {
            res.add(str);
        }


        /*本来回溯模板要遍历选择列表，但是本题的选择列表是两个独立的情况，所以单独写出来就好*/

        //加入到路径
        str=str+"(";
        //进入下一层决策
        backtrack(left - 1, right, str);
        //撤销选择
        str=str.substring(0,str.length()-1);

        //加入到路径
        str=str+")";
        //进入下一层决策
        backtrack(left, right - 1, str);
        //撤销选择
        str=str.substring(0,str.length()-1);
    }
}