生成集合的所有子集

在确定给定集合的所有子集时，元素的数量 (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 个子集。