Leetcode-22 Generate Parentheses

发表于 | 分类于 | 次

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1

1
2
3
4
5
6
7
8
n=3
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题思路

用回溯法构造括号字符串。构造过程中，不能出现右括号数量 r 大于左括号数量 l 的情况。可用的左括号数量与右括号数量均为 n。

复杂度分析

见 Leetcode 讨论区。

代码

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
class Solution {
	vector<string> res;
public:
	vector<string> generateParenthesis(int n) {
		string s(2 * n, '.');
		backtrack(s, 0, 0);
		return res;
	}

	void backtrack(string &s, int l, int r) {
		if (r > l) return; //当前右括号比左括号多,会导致括号字符串非法
		int n = s.size() / 2;
		if (l + r == 2 * n) { //括号用完且得到合法括号字符串,加入结果集
			res.push_back(s);
			return;
		}
		//左括号没用完,可选择左括号
		if (l < n) {
			s[l + r] = '(';
			backtrack(s, l + 1, r);
		}
		//右括号没用完,可选择右括号
		if (r < n) {
			s[l + r] = ')';
			backtrack(s, l, r + 1);
		}
	}
};