產生集合的所有子集

在決定給定集合的所有子集時，元素的數量(n) 起至關重要的作用。有效的演算法利用遞歸技術來實現此目的。

遞歸演算法

遞歸演算法的運作原理是，對於每個元素，子集可以分為兩個類別：包含該元素的類別和不包含該元素的類別。否則，這兩個分區共享相同的子集。

從 n=1 開始，我們有兩個子集：{}（空集）和 {1}。

對於 n>1，我們確定1,...,n-1 的子集並複製它們。一組將向每個子集添加 n，而另一組將保持不變。這兩個集合的並集產生子集的完整集合。

說明性範例

讓我們產生{1, 2, 3, 4, 5} 的子集：

• n=1: {{} , {1}}
• n=2: 將 {} 、 {1} 加 2。與{} 、 {1} 並集： {{} 、 {1} 、 {2 } , {1, 2}}
• n=3: 加3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: 加4: { {} 、 {1} 、 {2} 、 {1, 2} 、 {3} 、 {1, 3} 、 {2, 3} 、 {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , { 1, 2, 3, 4}}
• n=5: 加5 : {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3 , 4} , {1, 2, 3, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 5}, {3, 5}, {1, 3, 5}, {2, 3, 5}, { 1, 2, 3, 5}, {4, 5}, {1, 4, 5}, {2, 4, 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4, 5}}

因此，我們得到了 {1, 2, 3, 4, 5} 的所有 32 個子集。