力扣---22. 括号生成

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

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

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

提示：
    1 <= n <= 8
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

之前写过一次这道题，只不过因为当时对回溯等算法只是了解，远达不到应用的程度。这次又写了一次，终于是用回溯写出来了。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        tool(list, "", 0, 0, n);
        return list;
    }
    private void tool(List<String> list, String str, int l, int r, int n) {
        if (l > n || r > n || r > l) {
            return;
        }
        if (l == n && r == n) {
            list.add(str);
            return;
        }
        tool(list, str + '(', l + 1, r, n);
        tool(list, str + ')', l, r + 1, n);
    }
}

由于javaString不可改变的特点，不需要对string进行特殊的操作，用StringBuilder优化试试：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        tool(list, new StringBuilder(), 0, 0, n);
        return list;
    }

    public void tool(List<String> list, StringBuilder str, int l, int r, int n) {
        if (l == r && l == n) {
            list.add(str.toString());
            return;
        }
        if (l < n) {
            str.append('(');
            tool(list, str, l + 1, r, n);
            str.deleteCharAt(str.length() - 1);
        }
        if (r < l) {
            str.append(')');
            tool(list, str, l, r + 1, n);
            str.deleteCharAt(str.length() - 1);
        }
    }
}