1.题目

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

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

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

提示：
1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

2.思路

（1）递归
主要思想如下（来自网络）：
① n = 1 时，显然结果为 “()”；
② n = 2 时，我们可以在 n = 1 的基础上进行括号组合，将 n = 1 的结果进行拆解，得到"0 ( 1 ) 2"，即有 0，1，2 三个位置可以插入一个完整的 “()”，那么可以直接得到 “()()”，“(())”，“()()”，去重之后得到 “()()”，“(())”；
③ n = 3 时，同理对 n = 2 的所有结果进行拆解，在可以空缺的位置插入一个完整的 “()”，去掉重复的便得到了最终的结果；
…
显然要想求出 n 对括号所有的有效组合，那必须先求出 n - 1 对括号的结果，如此类推，进而要求出 n = 1 时的情况，而 n = 1 时的结果我们很容易求出，就是 “()”。所以我们可以使用递归的思想来进行求解。此外，需要注意的是，我们需要去掉重复结果，这一点可以使用 Java 中的 set 集合来解决。

（2）回溯算法
思路参考LeetCode官方题解。

3.代码实现（Java）

//思路1————递归
public List<String> generateParenthesis(int n) {
    if (n == 1) {
        return Arrays.asList("()");
    }
    HashSet<String> hashSet = new HashSet<>();
    for (String str : generateParenthesis(n - 1)) {
        for (int i = 0; i <= str.length() / 2; i++) {
            hashSet.add(str.substring(0, i) + "()" + str.substring(i, str.length()));
        }
    }
    return new ArrayList<>(hashSet);
}

//思路2————回溯算法
class Solution {
    
    // res 用于保存最终结果
    List<String> res = new ArrayList<>();
    // builder 保存中间结果
    StringBuilder builder = new StringBuilder();
    
    public List<String> generateParenthesis(int n) {
        backtrack(0, 0, n);
        return res;
    }
    
    /*
        leftCnt: 左括号的数量
        rightCnt: 右括号的数量
        n: 括号的对数
    */
    public void backtrack(int leftCnt, int rightCnt, int n) {
        //如果 builder 的长度 = 2 * n，说明已经找到了一种组合
        if (builder.length() == n * 2) { 
            res.add(builder.toString());
            return;
        }
        //如果左括号数量小于 n，可以放一个左括号
        if (leftCnt < n) {
            builder.append('(');
            backtrack(leftCnt + 1, rightCnt, n);
            builder.deleteCharAt(builder.length() - 1);
        }
        //如果右括号数量小于左括号的数量，可以放一个右括号
        if (rightCnt < leftCnt) {
            builder.append(')');
            backtrack(leftCnt, rightCnt + 1, n);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

原文链接：https://blog.csdn.net/weixin_43004044/article/details/123493807

LeetCode_递归_回溯算法_中等_22.括号生成

目录

1.题目

2.思路

3.代码实现（Java）