22. 括号生成

1. 题目

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 8

2. 思路

  • 初始化字符串结果集合result变量，同时采用回溯算法，如下：
1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

  • 其中回溯函数中，参数分别是字符串、左括号计数变量left与右括号计数变量right，当左括号计数变量或右括号计数变量大于目标括号数量时，将直接终止回溯（此时回溯已经没有意义了，因为无法构成期望字符串）

  • 当左右括号计数变量与目标括号数量一致时，说明已生成最终字符串，将其写入结果集合后终止回溯

  • 如果均不满足以上条件，且当left变量大于等于right变量（说明左边是有富余的左括号，可以进行后续回溯操作）

    • 先追加左括号，并进行下一层回溯，回溯完成后，移除刚刚加入的左括号
    • 随后追加右括号，并进行下一层回溯，回溯完成后，移除刚刚加入的右括号
    • （这一层回溯中，需要同步更新left变量和right变量）

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private int target;
    private List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        this.target = n;
        var str = new StringBuilder();
        helper(str, 0, 0);
        return result;
    }

    private void helper(StringBuilder str, int left, int right) {
        if (left > target || right > target) {
            return;
        }

        if (left - right == 0 && left == target) {
            result.add(str.toString());
            return;
        }

        if (left >= right) {
            str.append('(');
            helper(str, left + 1, right);
            str.deleteCharAt(str.length() - 1);

            str.append(')');
            helper(str, left, right + 1);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

4. 复杂度

  • 时间复杂度：未知
  • 空间复杂度：O(n)，空间主要消耗在递归层数

提交结果