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

 1 // 9.4 Return all subsets of a set
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 
 6 void getSubsets(const vector<int> &v, int idx, vector<int> &buffer, vector<vector<int> > &res)
 7 {
 8     if (idx == (int)v.size()) {
 9         res.push_back(buffer);
10     } else {
11         getSubsets(v, idx + 1, buffer, res);
12         buffer.push_back(v[idx]);
13         getSubsets(v, idx + 1, buffer, res);
14         buffer.pop_back();
15     }
16 }
17 
18 int main()
19 {
20     int i, j;
21     vector<vector<int> > res;
22     vector<int> v;
23     vector<int> buffer;
24     int n;
25     
26     while (scanf("%d", &n) == 1 && n > 0) {
27         v.resize(n);
28         for (i = 0; i < n; ++i) {
29             scanf("%d", &v[i]);
30         }
31         
32         getSubsets(v, 0, buffer, res);
33         
34         for (i = 0; i < (int)res.size(); ++i) {
35             printf("[");
36             for (j = 0; j < (int)res[i].size(); ++j) {
37                 if (j == 0) {
38                     printf("%d", res[i][j]);
39                 } else {
40                     printf(" %d", res[i][j]);
41                 }
42             }
43             printf("]
");
44             res[i].clear();
45         }
46         res.clear();
47         buffer.clear();
48         v.clear();
49     }
50     
51     return 0;
52 }