我正在准备面试，我在网上的“数学”类别下偶然发现了这个问题。
生成给定集合的幂集：
int A[] = {1,2,3,4,5};
int N = 5;
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) {
for ( int j = 0; j < N; j++) {
if ( (i >> j) & 1 )
cout << A[j];
}
cout <<endl;
}
请我不要一个明确的答案。我只是想要关于如何解决这个问题的澄清和提示。
我在谷歌上检查了功率集算法，但我仍然不明白如何解决这个问题。
另外，有人可以重申这个问题的要求。
谢谢你。
Power set of a set A is the set of all of the subsets of A.
不是世界上最友好的定义，但一个例子会有所帮助：
例如。对于{1, 2}，子集是 ：{}, {1}, {2}, {1, 2}
因此，功率集是{{}, {1}, {2}, {1, 2}}
让这个决定由一个位（1/0）表示。
因此，要生成{1}，您将选择1和丢弃2(10)。
在类似的行上，您可以为所有子集编写一个位向量：
重申：如果通过包含原始集合的部分或全部元素而形成的子集。因此，要创建一个子集，您需要访问每个元素，然后决定是保留它还是删除它。这意味着对于每个元素，您有 2 个决定。因此，对于一个集合，您最终可以2^N做出不同的决策，对应于2^N不同的子集。
看看你能不能从这里取走。
创建一个幂集：
{"A", "B", "C"}。
伪代码：
val set = {"A", "B", "C"}
val sets = {}
for item in set:
for set in sets:
sets.add(set + item)
sets.add({item})
sets.add({})
算法解释：
1）初始化sets为一个空集：{}。
2）遍历每个项目{"A", "B", "C"}
3) 遍历set您的sets.
3.1) 创建一个新集合，它是set.
3.2) 将 附加item到new set.
3.3) 附加new set到sets.
4) 添加item到您的sets.
4) 迭代完成。将空集添加到您的resultSets.
演练：
再来看看sets每次迭代后的内容：
迭代 1，项目 = “A”：
sets = {{"A"}}
迭代 2，项目 =“B”：
sets = {{"A"}, {"A", "B"}, {"B"}}
迭代 3，项目 =“C”：
sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}}
迭代完成，添加空集：
sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}, {}}
集合的大小是 2^|set| = 2^3 = 8 这是正确的。
Java中的示例实现：
public static <T> List<List<T>> powerSet(List<T> input) {
List<List<T>> sets = new ArrayList<>();
for (T element : input) {
for (ListIterator<List<T>> setsIterator = sets.listIterator(); setsIterator.hasNext(); ) {
List<T> newSet = new ArrayList<>(setsIterator.next());
newSet.add(element);
setsIterator.add(newSet);
}
sets.add(new ArrayList<>(Arrays.asList(element)));
}
sets.add(new ArrayList<>());
return sets;
}
输入： [A, B, C]
输出：[[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]
幂集只是给定集合的所有子集的集合。它包括所有子集（带有空集）。众所周知，这个集合中有 2 N个元素，其中N是原始集合中元素的数量。
要构建电源组，可以使用以下内容：
N位（对于较小的数字，添加前导零）。如果某个集合成员包含在当前子集中，则每个位都对应。例如，3 个数字：a, b,c
number binary subset
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}
好吧，您需要生成所有子集。对于一个大小为 n 的集合，有 2 n个子集。
一种方法是迭代从 0 到 2 n - 1 的数字，并将每个数字转换为二进制数字列表，其中0意味着排除该元素而1意味着包括它。
另一种方法是递归，分而治之。
生成集合的所有组合（通过包含或不包含项目）。举例说明：一组（或列表）中的 3 个项目。可能的子集将是：
000
100
010
001
110
101
011
111
结果是 2^（集合中的元素数）。
因此，我们可以生成 N 个项目的所有组合（使用 python），如下所示：
def powerSet(items):
N = len(items)
for i in range(2**N):
comb=[]
for j in range(N):
if (i >> j) % 2 == 1:
comb.append(items[j])
yield comb
for x in powerSet([1,2,3]):
print (x)
通过实施评分最高的答案，您会得到类似的结果。
def printPowerSet(set,set_size):
# set_size of power set of a set
# with set_size n is (2**n -1)
pow_set_size = (int) (math.pow(2, set_size));
counter = 0;
j = 0;
# Run from counter 000..0 to 111..1
for counter in range(0, pow_set_size):
for j in range(0, set_size):
# Check if jth bit in the
# counter is set If set then
# pront jth element from set
if((counter & (1 << j)) > 0):
print(set[j], end = "");
print("");
C# 解决方案
时间复杂度和空间复杂度：O(n*2^n)
public class Powerset
{
/*
P[1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
*/
public List<List<int>> PowersetSoln(List<int> array)
{
/*
We will start with an empty subset
loop through the number in the array
loop through subset generated till and add the number to each subsets
*/
var subsets = new List<List<int>>();
subsets.Add(new List<int>());
for (int i = 0; i < array.Count; i++)
{
int subsetLen = subsets.Count;
for (int innerSubset = 0; innerSubset < subsetLen; innerSubset++)
{
var newSubset = new List<int>(subsets[innerSubset]);
newSubset.Add(array[i]);
subsets.Add(newSubset);
}
}
return subsets;
}
}
示例 Java 代码：
void printPowerSetHelper(String s, String r) {
if (s.length() > 0) {
printPowerSetHelper(s.substring(1), r + s.charAt(0));
printPowerSetHelper(s.substring(1), r);
}
if (r.length() > 0) System.out.println(r);
}
void printPowerSet(String s) {
printPowerSetHelper(s,"");
}