給出一個(gè)集合，如(1, 2, 3, 4)，打印出該集合的所有子集
分析一下問(wèn)題，子集是指取原集合中的任意多個(gè)元素，轉(zhuǎn)化一下問(wèn)題，就是對(duì)于原集合中的任何一個(gè)元素，我們都有兩個(gè)選擇，包含或者不包含，所以對(duì)于n個(gè)元素的集合，其子集數(shù)為： 2*2*2... = 2^n。那么可以得出其遞歸算法：
01 void Recursive_Subsets(int* a, bool* b, int start, int end)
02 {
03 if (start <= end)
04 {
05 // determine current number's status, which has 2 choices
06 // and then continue with left ones
07 b[start] = true;
08 Recursive_Subsets(a, b, start+1, end);
09
10 b[start] = false;
11 Recursive_Subsets(a, b, start+1, end);
12 }
13 else
14 {
15 for (int i = 0; i <= end; i++)
16 {
17 if (b[i]) cout << a[i];
18 }
19 cout << endl;
20 }
21
22 }
23
24 void PrintAllSubsets1(int* a, int n)
25 {
26 bool* b = new bool[n];
27 Recursive_Subsets(a, b, 0, n-1);
28 delete b;
29 }
遞歸的優(yōu)點(diǎn)是直觀、易懂：寫起來(lái)如此，讀起來(lái)也是這樣。但是每次遞歸都是call stack的不斷疊加，對(duì)于這個(gè)問(wèn)題，其需要消耗O(n)的�？臻g，�？臻g，�？臻g~~~
于是，我們也可以將其轉(zhuǎn)化成循環(huán)的方式來(lái)實(shí)現(xiàn)：
01 void PrintAllSubsets2(int* a, int n)
02 {
03 // Initialize flags as false
04 bool* b = new bool[n];
05 for(int i = 0; i < n; i++)
06 {
07 b[i] = false;
08 }
09
10 // Use 2 loops to enumerate all possible combinations of (each item's status * number of items),
11 // in this case: ([true|false] * size of set)
12 while(true)
13 {
14 // Get one solution, output it!
15 for(int i = 0; i < n; i++)
16 {
17 if(b[i]) cout << a[i];
18 }
19 cout << endl;
20
21
22 // One of the number's status has switched, start over enumeration for that!
23 // ex: I have following enumeration for 3 numbers:
24 // 0, 0, 0
25 // 0, 0, 1
26 // 0, 1, 0
27 // 0, 1, 1
28 // now if I changed the first number's status from 0 to 1, I need to re-enumerate the other 2 numbers
29 // to get all possible cases:
30 // 1, 0, 0
31 // 1, 0, 1
32 // 1, 1, 0
33 // 1, 1, 1
34 int k = n - 1;
35
36 while(k >= 0)
37 {
38 if(b[k] == false) // have we tried all possible status of k?
39 {
40 b[k] = true; // status switch, as we only have 2 status here, I use a boolean rather than an array.
41 break; // break to output the updated status, and further enumeration for this status change, just like a recursion
42 }
43 else // We have tried all possible cases for k-th number, now let's consider the previous one
44 {
45 b[k] = false; // resume k to its initial status
46 k--; // let's consider k-1
47 }
48 }
49
50 if(k < 0) break; // all the numbers in the set has been processed, we are done!
51 }
52
53 // clean up
54 delete [] b;
55 }
詳細(xì)如何轉(zhuǎn)換在注釋中已經(jīng)說(shuō)明，對(duì)于這類窮舉狀態(tài)的遞歸程序，我們可以將這個(gè)程序的框架當(dāng)做一個(gè)模式，照樣子來(lái)轉(zhuǎn)化即可。
喜歡 
頂
難過(guò)
囧
圍觀
無(wú)聊
