面试金典--9.6

题目描述：实现一种算法，打印n对括号的全部有效组合

思路：递归，不合法状态就是right<left；其他情况加入左右括号分别递归

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 using namespace std;
 8 
 9 vector<string> res;
10 void addParen(int left,int right,string ans)
11 {
12     if(left <0 || right < left)
13     {
14         return;
15     }
16     if(left ==0 && right == 0)
17     {
18         res.push_back(ans);
19         //return;
20     }
21     else
22     {
23         if(left > 0)
24         {
25             string ans1 = ans+'(';
26             addParen(left-1,right,ans1);
27         }
28         if(right > left)
29         {
30             string ans1 = ans+')';
31             addParen(left,right-1,ans1);
32         }
33     }
34 }
35 
36 int main()
37 {
38     string s;
39     addParen(3,3,s);
40     vector<string>::iterator it = res.begin();
41     while(it != res.end())
42     {
43         cout<<*it<<endl;
44         it++;
45     }
46     return 0;
47 }