稻森千惠,丰台总部基地,我们结婚了20130622
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
看到该题目我首先的想法是采用递推的方式去实现该题目，但是发现会生成重复的元素，因此我采用了dfs剪去不合适的分支的方法来处理该题目。需要剪枝的情况有三种，左括号数目大于n，右括号数目大于n，左括号数目小于右括号数目，这里我们重点说一下第三种情况，因为在括号序列中，一定是先生成左括号再生成右括号，因此一定是左括号的数目大于等于右括号的数目，否则就会出错。程序代码如下：
我要评论#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> generateparenthesis(int n);
void func(vector<string>& res, string str, int l, int r, int n);
int main()
{
int n;
cin >> n;
vector<string> ans = generateparenthesis(n);
for (int i = 0; i < ans.size(); ++i)
{
cout << ans[i] << endl;
}
return 0;
}
vector<string> generateparenthesis(int n) {
vector<string> res;
func(res, "", 0, 0, n);
return res;
}
void func(vector<string>& res, string str, int l, int r, int n) {
if (l > n || r > n || r > l)
return;
if (l == n && r == n)
{
res.push_back(str);
return;
}
func(res, str + '(', l + 1, r, n);
func(res, str + ')', l, r + 1, n);
return;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论