Find Power Set Using Java

幂集 是指一个集合中所有可能的子集的集合，包括空集和原集合本身。如果一个集合包含 n 个元素，那么它的幂集将包含 2^n 个子集。这是因为集合中的每个元素都可以选择包含或不包含在子集中，总共有 2^n 种可能的组合。

输入: s = "abcd"

输出: "", "a", "b", "c", "d", "ab", "ac", "ad", "bc", "bd", "cd", "abc", "abd", "acd", "bcd", "abcd"

输入: s = "pq"

输出: "", "p ", "q", "pq" 输入: s = "w"

输出: "", "w"

使用二进制表示法

二进制表示法通过将 0 到 2^n - 1 的每个数字视为一个二进制掩码来形成幂集，其中每个位指示一个元素是否属于子集。这种 方法有效地探究了集合中元素的每一种潜在组合。

算法

步骤 1: 使用 1 << nums.length 计算子集的总数，即 2n2^n2n。

步骤 2: 循环从 0 到 2^n - 1，代表每个子集。

步骤 3: 对于每个数字，检查每一位，以确定是否应将相应的元素包含在子集中。

步骤 4: 将生成的子集添加到所有子集的列表 (powerSet) 中。

步骤 5: 返回完整的幂集并打印每个子集。

实施

文件名: PowerSetBinary.java

输出

 
Power Set:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]  

复杂度

时间复杂度: O(N * 2^N)

辅助空间复杂度: O(N * 2^N)

前一个排列方法

前一个排列方法通过从最大的子集开始，并使用字典序系统地移动到较小的子集来生成子集。当需要按反向顺序或特定序列探索子集时，此方法非常有用。

算法

步骤 1: 创建一个空的列表 powerSet 来存储所有子集。

设置 mask = (1 << n) - 1，表示包含所有元素的最大的子集。

步骤 2: 当 mask >= 0 时，创建一个新的空列表 subset。

步骤 3: 对于从 0 到 n-1 的每个索引 j，检查 mask 的第 j 位是否为 1。

如果为 1，则将 nums[j] 添加到 subset 中。

步骤 4: 将生成的 subset 添加到 powerSet 中。

步骤 5: 将 mask 减 1 (mask--)，并重复此过程，直到生成所有子集。

最后，返回 powerSet。

实施

文件名: PowerSetPreviousPermutation.java

输出

 
Power Set:
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]   

复杂度

时间复杂度: O(N * 2^N)

辅助空间复杂度: O(N * 2^N)

使用树表示法

文件名: PowerSetTree.java

输出

 
Power Set:
[a, b, c]
[a, b]
[a, c]
[a]
[b, c]
[b]
[c]
[]   

复杂度

时间复杂度: O(N * 2^N) 生成 2^N 个子集，每个子集需要 O(N) 时间构建。

辅助空间复杂度: O(N)