大家好！我是曾续缘😚
今天是《LeetCode 热题 100》系列
发车第 59 天
回溯第 5 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
难度：💖💖

解题方法

我们需要生成所有有效的括号组合，也就是需要生成n个左括号和n个右括号，左括号的数量要等于右括号的数量，并且在任何位置，左括号的数量都不能小于右括号的数量，因为是先有左括号再有右括号。

我们可以使用回溯算法来解决这个问题。

定义一个递归函数 backtrack，传入四个参数：当前正在生成的字符串 sb、当前左括号的数量 cur_l、当前右括号的数量 cur_r、以及目标括号对数 n。

在每一步中，我们有两种选择：添加左括号或者添加右括号。

如果左括号数量小于目标数量，可以添加左括号
如果右括号数量小于左括号数量，可以添加右括号
当左括号数量和右括号数量均达到目标数量时，将当前生成的字符串加入答案列表中

Code

查看代码

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder("");
        backtrack(n, 0, 0, ans, sb);
        return ans;
    }
    
    void backtrack(int n, int cur_l, int cur_r, List<String> ans, StringBuilder sb){
        // 当左括号数量和右括号数量均达到目标数量时，将当前生成的字符串加入答案列表中
        if(cur_l == cur_r && n == cur_l){
            ans.add(sb.toString());
            return;
        }
        // 如果左括号数量小于目标数量，可以添加左括号
        if(cur_l < n){
            sb.append("(");
            backtrack(n, cur_l + 1, cur_r, ans, sb);
            sb.deleteCharAt(sb.length() - 1); // 回溯，删除刚刚添加的左括号
        }
        // 如果右括号数量小于左括号数量，可以添加右括号
        if(cur_l > cur_r){
            sb.append(")");
            backtrack(n, cur_l, cur_r + 1, ans, sb);
            sb.deleteCharAt(sb.length() - 1); // 回溯，删除刚刚添加的右括号
        }
    }
}

解题方法 ​

Code ​

解题方法

Code