Generate Parentheses

佚名 6年前 (2019-05-06) 随笔 2016人围观抢沙发百度已收录

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

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

code

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    void backtrack(vector<string> &res,string tmp,int leftNum,int rightNum,const int N)
    {
        if(leftNum==0&&rightNum==0)
        {
            res.push_back(tmp);
            return ;
        }
        if(leftNum>0)
        {
            backtrack(res,tmp.append("("),leftNum-1,rightNum,N);
            tmp.pop_back();
        }
        if(leftNum==N)
            return ;
        if(leftNum<rightNum&&rightNum>0)
        {
            backtrack(res,tmp.append(")"),leftNum,rightNum-1,N);
            tmp.pop_back();
        }
        return ;
    }
    vector<string> generateParenthesis(int n)
    {
        vector<string> res;
        if(n<=0)
            return res;

        backtrack(res,"",n,n,n);
        return res;
    }

};

int main()
{
    Solution s;
    vector<string> res(s.generateParenthesis(4));
    for(auto i:res)
        cout<<i<<endl;
    cout<<endl;
    return 0;
}