时间轴

2025-11-30

init

题目：

P22 括号生成

https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-interview-150

暴力回溯方法，最后去重

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
33
34
35
36
#include <vector>
#include <string>
#include <algorithm>

using std::string;
using std::vector;

#define PARENTHESE "()"

class Solution {
    private:
	void backtrace(string &track, vector<string> &res, int n)
	{
		if (track.size() == n * 2) {
			res.push_back(track);
			return;
		}
		int i, len = track.size();
		for (i = 0; i < len; i++) {
			track.insert(i, PARENTHESE);
			backtrace(track, res, n);
			track.erase(i, 2);
		}
	}

    public:
	vector<string> generateParenthesis(int n)
	{
		vector<string> res;
		string track(PARENTHESE);
		backtrace(track, res, n);
		std::sort(res.begin(), res.end());
		res.erase(std::unique(res.begin(), res.end()), res.end());
		return res;
	}
};

上面这种方法性能较低，原因是我们生成了大量重复的结果，最后还要过滤重复的。

如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
搜索树如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"" (3,3)
|
'(' -> "(" (2,3)
|   '(' -> "((" (1,3)
|   |   '(' -> "(((" (0,3)
|   |   |   ')' -> "((()" (0,2)
|   |   |   |   ')' -> "((())" (0,1)
|   |   |   |   |   ')' -> "((()))" ✅
|   |   ')' -> "(()" (1,2)
|   |   |   '(' -> "(()(" (0,2)
|   |   |   |   ')' -> "(()()" (0,1)
|   |   |   |   |   ')' -> "(()())" ✅
|   |   ')' -> "(())" (1,1)
|   |   |   '(' -> "(())(" (0,1)
|   |   |   |   ')' -> "(())()" ✅
'(' -> "()" (2,2)
|   '(' -> "()(" (1,2)
|   |   '(' -> "()((" (0,2)
|   |   |   ')' -> "()(())" ✅
|   ')' -> "()" (2,2) (不生成非法)

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
33
34
35
36
37
#include <vector>
#include <string>

using std::string;
using std::vector;

class Solution {
    private:
	void backtrace(string &track, vector<string> &res, int left, int right)
	{
		if (left == 0 && right == 0) {
			return res.push_back(track);
		}

		if (left > 0) {
			track.push_back('(');
			backtrace(track, res, left - 1, right);
			track.pop_back();
		}

		if (right > left) { // right must be more than left
			track.push_back(')');
			backtrace(track, res, left, right - 1);
			track.pop_back();
		}
	}

    public:
	vector<string> generateParenthesis(int n)
	{
		vector<string> res;
		string track;
		backtrace(track, res, n, n);
		return res;
	}
};