括号生成

题目描述

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

数据样例

示例 1：

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

示例 2：

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

提示：

  • $1 \leq n \leq 8$

深度优先搜索 DFS - $O(4 ^ N)$

题目的 数据范围很小，因此可以考虑暴力搜索

DFS 搜索过程：

  • 可以将问题看成：将括号放入长度为 $2 * n$ 个空位中。可以依次看每个空位。
  • 每个空位有两种选择：(, )

为了便于大家理解，DFS 搜索空间树 如下图所示：

那么我们知道，不是所有最终搜索得到的序列都是满足条件的，如图中所示：

  • 标注红色序列为合法序列
  • 标注黑色序列为不合法序列

因此需要将不合法的序列去掉，图中的 紫色部分 是为了去掉所有不合法的括号序列：

  • 由于左括号和右括号数量相同，那么左括号应该有 $n$ 个，同时右括号也有 $n$ 个
  • 如果当前得到的序列中，右括号数量大于左括号数量，那么当前序列就是不合法的

通过上述两个点，我们在搜索中进行对应的处理，即可使得搜索到的所有序列均是合法的。

具体可以结合代码和上述图进行理解。

时间复杂度 - $O(4 ^ N)$

由于每个位置有两个位置可以选择，因此一共需要搜索 $2 ^ {2N} = 4 ^ N$ 个节点，因此时间复杂度为：$O(4 ^ N)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func generateParenthesis(n int) []string {
    res = []string{}
    dfs(n, 0, 0, 0, "")
    return res
}

var res []string

// n：题目给定的括号对数，u：枚举所有的空位
// ls：左括号数量，rs：右括号数量
// cur：当前所有空位组成的字符串
func dfs(n int, u int, ls int, rs int, cur string) {
    // 如果枚举到最后一个空位，那么此时全部空位已经填完，结束递归
    if u >= 2 * n { res = append(res, cur); return }
    // 如果左括号数量不到一半，那么可以在当前空位填入左括号。与图中紫色部分对应。
    if ls < n { dfs(n, u + 1, ls + 1, rs, cur + "(") }
    // 如果当前右括号比左括号数量少，那么可以填入右括号。与图中紫色部分对应。
    if rs < ls { dfs(n, u + 1, ls, rs + 1, cur + ")") }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int n;
    vector<string> res;

    void dfs(int n, int u, int ls, int rs, string cur) {
        if (u >= 2 * n) {
            res.push_back(cur);
            return ;
        }
        if (ls < n) dfs(n, u + 1, ls + 1, rs, cur + '(');
        if (rs < ls) dfs(n, u + 1, ls, rs + 1, cur + ')');
    }

    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, 0, "");
        return res;
    }
};