《Cracking the Coding Interview》——第9章：递归和动态规划——题目6

 1 // 9.6 Print all valid parentheses sequences of n ()s.
 2 #include <iostream>
 3 #include <string>
 4 #include <vector>
 5 using namespace std;
 6 
 7 void DFS(int idx, int n, string s, vector<vector<string> > &result)
 8 {
 9     if (idx == n) {
10         result[n].push_back(s);
11         return;
12     } else {
13         int i, j;
14         for (i = 1; i <= n - idx; ++i) {
15             for (j = 0; j < (int)result[i - 1].size(); ++j) {
16                 DFS(idx + i, n, s + ‘(‘ + result[i - 1][j] + ‘)‘, result);
17             }
18         }
19     }
20 }
21 
22 int main()
23 {
24     vector<vector<string> > result;
25     int n;
26     int i;
27     
28     result.resize(1);
29     result[0].push_back("");
30     
31     while (cin >> n && n > 0) {
32         if (n >= (int)result.size()) {
33             for (i = (int)result.size(); i <= n; ++i) {
34                 result.push_back(vector<string>());
35                 DFS(0, i, "", result);
36             }
37         }
38         for (i = 0; i < (int)result[n].size(); ++i) {
39             cout << result[n][i] << endl;
40         }
41     }
42     
43     return 0;
44 }