问题描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
解决方案
首先想到了二叉树。使用深度遍历，向左走加(，向右走加)，压入合适的字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<string> v;
void dfs(string s,int val,int n,int count)
{
if (count == n && val == 0)
v.push_back(s);
else if (count>n||val < 0)
return;
else
{
dfs(s + "(",val + 1, n, count + 1);
dfs(s + ")",val - 1, n, count);
}
}
vector<string> generateParenthesis(int n) {
dfs("", 0, n, 0);
return v;
}
|