LeetCode#22 - 括号生成

Posted on In , , Word count in article: 332 Reading time ≈ 1 mins.
  • 闲来无事，随便写一道

题目大意

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

示例 1:

输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入: n = 1
输出: ["()"]

提示:

  • 1 <= n <= 8

思路

  • 显然，当 左括号数 = n 时，我们仅添加右括号以实现括号对匹配，所得结果即为一个 有效组合
  • 当 左括号数 < n 时，有 两种 情况
    • 当 左括号数 > 右括号数 时，我们可以在右侧添加一个 右括号
    • 直接添加一个 左括号

以 n = 3 为例，如图所示

n=3

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void recur(string s, int l, int r, int n, vector<string>& res) {
        if (l < n) {
            recur(s + "(", l + 1, r, n, res);       // 直接加左括号
            if (l > r)
                recur(s + ")", l, r + 1, n, res);   // 加右括号
        } else {
            string t = s;
            while ((int)t.size() < n * 2) {
                t += ")";                           // 右括号匹配
            }
            res.push_back(t);
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        recur("", 0, 0, n, ans);
        sort(ans.begin(), ans.end());   // 排序，使顺序与答案一致
        return ans;
    }
};

代码分析

  • 显然，这是在找一颗树的所有叶节点，实际上这个算法是 DFS

这个算法与力扣官方题解的 方法二 类似 括号生成，具体复杂度分析较为复杂，本文不做讨论。