Killing LeetCode [22] 括号生成

Description

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

Intro

Ref Link：https://leetcode.cn/problems/generate-parentheses/
Difficulty：Medium
Tag：String，Back Tracking
Updated Date：2023-09-08

Test Cases

示例1:

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

示例 2：

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

提示：

1 <= n <= 8
1

思路

• 思路：回溯算法
• 题目说 有效的括号组合必然左括号数量大于右括号的时候，才能放置右括号，不然就是无效的括号
• 如果左括号数量不大于 n，我们可以放一个左括号；
• 如果右括号数量小于左括号的数量，我们可以放一个右括号；

Code AC

class Solution {

    public List generateParenthesis(int n) {
        List result = new ArrayList<>();
        if (n <= 0) return result;
        backTracking("", result, n, 0, 0);
        return result;
    }

    public void backTracking(String str, List result, int size, int leftNum, int rightNum) {
        if (leftNum == size && rightNum == size) {
            result.add(str);
            return;
        }
        if (leftNum < size) {
            backTracking(str+"(", result, size, leftNum + 1, rightNum);
        }
        if (rightNum < size && leftNum > rightNum) {
            backTracking(str+")", result, size, leftNum, rightNum+1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Accepted

8/8 cases passed (1 ms)
Your runtime beats 72.75 % of java submissions
Your memory usage beats 39.74 % of java submissions (41.2 MB)
1
2
3

复杂度分析

• 时间复杂度：，在回溯过程中，每个答案需要 O(n)的时间复制到答案数组中。
• 空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1)的空间，最多递归 2n层，因此空间复杂度为 O(n)。