Medium | LeetCode 22. 括号生成 | 回溯

22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

解题思路

方法一： 回溯算法

在递归的同时, 将当前要添加括号的下标, 当前的左括号和右括号的数量作为参数传进去, 以便于判断递归的出口, 以及进行剪枝操作。

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(0, 0, n, new StringBuilder(), res);
    return res;
}

public void backtrack(int left, int right, int n, StringBuilder cur, List<String> res) {
    // 递归出口
    if ((left == right) && left == n) {
        res.add(cur.toString());
        return;
    }
    
    // 先添加左括号
    if (left < n) {
        cur.append("(");
        backtrack(left + 1, right, n, cur, res);
        // 还原刚刚添加的左括号
        cur.deleteCharAt(cur.length()-1);
    }
    
    // 然后尝试添加右括号
    if (right < left) {
        cur.append(")");
        backtrack(left, right+1, n, cur, res);
        // 还原刚刚添加的右括号
        cur.deleteCharAt(cur.length()-1);
    }
}