[leetCode]Generate Parentheses

 1  1 #include <string>
 2  2 #include <vector>
 3  3 #include <set>
 4  4 using namespace std;
 5  5 class Solution {
 6  6 public:
 7  7     set<string> strset; 
 8  8     vector<string> generateParenthesis(int n) {
 9  9         string s = "";
10 10         vector<string> ret;
11 11         if(n <= 0) return ret;
12 12         generate(n,s,0,ret);
13 13         return ret;
14 14     }
15 15     void generate(int n, string s, int index, vector<string> &ret){
16 16         s.insert(index,"()");
17 17         if(strset.find(s) != strset.end()) return;// get TLE without this sentence;
18 18         strset.insert(s);
19 19         if(n <= 1){
20 20             ret.push_back(s);    
21 21         }else{
22 22             for(int i = 0; i < s.length(); i++){
23 23                 generate(n-1,s,i,ret);
24 24             }
25 25         }
26 26     }
27 27 };