Generate Parentheses

Generate Parentheses Add to List
Description Submission Solutions
Total Accepted: 129826
Total Submissions: 305733
Difficulty: Medium
Contributors: Admin
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:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
使用递归得思想，主要是

if(left<n)//对于左括号，只要没超过个数什么时候都可以插入
  {s.push_back('(');
  generate(res,s,left+1,right,n);
  s.pop_back();//在递归回来之后应该将刚刚插入得进行删除
  }
if(right<left)//在右括号得个数小于左括号得个数时候可以进行右括号得插入
{s.push_back(')');
 generate(res,s,left,right+1,n);
  s.pop_back();//删除
}

class Solution {
public:s
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string s;
        generate(res,s,0,0,n);
        return res;
    }
    void generate(vector<string>&res,string s,int left,int right,int n)
    {
        if(left==n&&right==n)
     {res.push_back(s);
     return;
     }
      if(left<n)
        {s.push_back('(');
        generate(res,s,left+1,right,n);
        s.pop_back();
        }
    if(right<left)
    {s.push_back(')');
       generate(res,s,left,right+1,n);
        s.pop_back();
    }
    }
};