algorithm - 生成列表不同长度的每个幂集的算法？

Question

给定一个列表{x1, x2, x3, x4, ..., xn}，是否有一种算法可以生成该列表的每个子集？在这种情况下，子集的长度必须i为1 <= i <= n。排序也无关紧要，例如 this is a duplicate:{x3, x4, x9}与 相同{x9, x3, x4}，即不要将重复项放在输出中。此外，算法的运行时间必须是O(n^k)某个常数整数k>=0。

有谁知道如何做到这一点？

谢谢。

Answer 1

原始集合的每个元素在任何给定的子集中都可能存在或不存在。对于 n 元素列表，依次遍历 n 位二进制数，选择对应于 1 的元素。0b000...000 是空子集。0b111...111 是原始集。中间的每个数字都是一个可能的子集。所有可能的子集将在列表中包含一次且仅一次。

例如，如果原始集合是 {A, B, C}：

0 -> 000 -> {}
1 -> 001 -> {C}
2 -> 010 -> {B}
3 -> 011 -> {B, C}
4 -> 100 -> {A}
5 -> 101 -> {A, C}
6 -> 110 -> {A, B}
7 -> 111 -> {A, B, C}

如果您只需要特定长度的子集，则使用二进制 1 计数算法之一来消除那些不匹配的数字/子集。生成数字 0 到 n 显然是 O(n)。这将其归结为您使用的二进制 1 计数算法。由于没有产生任何重复，因此无需消除重复。

Answer 2

做一些关于回溯的谷歌搜索。这是你问的标准问题。