Cover image for Interview Classic 150 Questions P22 Generate Parentheses

Interview Classic 150 Questions P22 Generate Parentheses

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-11-30

init

Title:

P22 Generate Parentheses

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

Brute force backtracking method, finally deduplicate

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;
	}
};

The above method has low performance because we generate a large number of duplicate results and finally need to filter duplicates.

Another method: consider the following:

If the number of left parentheses is not greater than n, we can place a left parenthesis. If the number of right parentheses is less than the number of left parentheses, we can place a right parenthesis.

The search tree is as follows:

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
38
39
40
41
42
43
"" (3,3)
│
├─ "(" (2,3)
│  │
│  ├─ "((" (1,3)
│  │  │
│  │  ├─ "(((" (0,3)
│  │  │  │
│  │  │  └─ "((()" (0,2)
│  │  │      │
│  │  │      └─ "((())" (0,1)
│  │  │          │
│  │  │          └─ "((()))" (0,0) ✅
│  │  │
│  │  └─ "(()" (1,2)
│  │      │
│  │      ├─ "(()(" (0,2)
│  │      │  │
│  │      │  └─ "(()()" (0,1)
│  │      │      │
│  │      │      └─ "(()())" (0,0) ✅
│  │      │
│  │      └─ "(())" (1,1)
│  │          │
│  │          └─ "(())(" (0,1)
│  │              │
│  │              └─ "(())()" (0,0) ✅
│  │
│  └─ "()" (2,2)
│      │
│      └─ "()(" (1,2)
│          │
│          ├─ "()((" (0,2)
│          │  │
│          │  └─ "()(()" (0,1)
│          │      │
│          │      └─ "()(())" (0,0) ✅
│          │
│          └─ "()()" (1,1)
│              │
│              └─ "()()(" (0,1)
│                  │
│                  └─ "()()()" (0,0) ✅

The code is as follows:

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;
	}
};

LeetCode Hot 100 rewrite, did not think of pruning method:

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
38
39
40
41
42
43
44
45
#include <vector>
#include <string>
#include <algorithm>

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


class Solution {
    private:
        void __generateParentesis(vector<string> &res, string &curr, int nr_par, int pos)
        {
                if (curr.size() == 2 * nr_par) {
                        res.push_back(curr);
                        return;
                }

                int i, n = curr.size();
                for (i = pos; i < n; i++) {
                        curr.insert(i, "()");
                        __generateParentesis(res, curr, nr_par, pos + 1);
                        curr.erase(i, 2);
                }
        }

    public:
        vector<string> generateParenthesis(int n)
        {
                // 1 <= n <= 8
                vector<string> res;
                string curr = "()";
                if (n == 1) {
                        res.push_back(curr);
                        return res;
                }

                __generateParentesis(res, curr, n, 0);

                std::sort(res.begin(), res.end());
                res.erase(std::unique(res.begin(), res.end()), res.end());


                return res;
        }
};