欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

括号生成

程序员文章站 2022-06-22 07:55:15
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 看到该题目我首先的想法是采用递推的方式去实现该题目,但是发现会生成重复的元素,因此我采用了dfs剪去不合适的分支的方法来处理该题目。需要剪枝的情况有三种,左括号数目大于n,右括号数目大于n,左括号数目小于 ......

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