leetcode22.括号生成

Posted on | In |
Words count in article: 205 | Reading time ≈ 1

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

示例：

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

分析：

1
2
3
4
5
搜索顺序：
	从""开始按位搜
剪枝条件：
	1、左括号数量 < 右括号数量
	2、左/右括号数量 > n

代码

  • C++

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
class Solution {
public:

    vector<string> res;

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

        return res;
    }

    void dfs(int n, int lc, int rc, string path) {
        if (lc == n && rc == n)  {
            res.push_back(path);
            path.clear();
            return;
        }
        if (lc < rc) return;
        if (lc > n || rc > n) return;

        path += "(";
        dfs(n, lc + 1, rc, path);
        path.pop_back();

        path += ")";
        dfs(n, lc, rc + 1, path);
        path.pop_back();
    }
};

[原题链接](22. 括号生成 - 力扣（Leetcode）)

0%