Java 中显示整数数组的所有子集

给定一个整数数组（或数组列表）。我们的任务是打印给定整数数组的所有子集（不包括空集）。请注意，显示子集的顺序无关紧要。

示例 1

输入

int inputArr[] = {1, 2, 3}

输出 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

示例 2

输入

int inputArr[] = {1, 2, 3, 4, 5}

输出 {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, (1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}

方法：使用回溯

通过回溯，我们可以生成给定数组的所有子集。对于每个元素，我们只有两个选择。一个是将该元素包含在当前子集中。另一个是将该元素从当前子集中排除。通过这种方式，我们可以生成给定整数数组的所有子集。

步骤如下

步骤 1：创建一个二维数组列表 answer 用于存放所有子集。

步骤 2：同时创建一个列表 tmp 用于存放当前子集。

步骤 3：创建一个递归方法 getSubset()，该方法具有以下四个参数。

步骤 4：一个用于存放当前索引。第二个用于存储当前子集。第三个用于存储所有生成的子集（二维列表），第四个是输入数组。

步骤 5：使用当前索引 0、空当前向量（最初将没有任何子集）、空二维列表和输入整数数组来调用该方法。

步骤 6：在 getSubset() 方法中，我们将 i 元素包含到列表 tmp 中，并递归调用 getSubset()，参数为 i + 1。

步骤 7：当方法调用返回时，我们从 tmp 列表中删除 i 元素，然后再次使用 i + 1 调用 getSubset() 方法。

步骤 8：如果 i 的值与输入数组的大小相同，则将列表 tmp 添加到列表 answer 中。

步骤 9：最后，对列表 answer 中的每个子数组进行排序并显示。

现在让我们看看上述步骤的实现。

文件名： SubsetIntArr.java

输出

For the array list: [1, 2, 3] 

The subsets are: 
[ 1 2 3 ]
[ 1 2 ]
[ 1 3 ]
[ 1 ]
[ 2 3 ]
[ 2 ]
[ 3 ]

For the array list: [1, 2, 3, 4, 5] 

The subsets are: 
[ 1 2 3 4 5 ]
[ 1 2 3 4 ]
[ 1 2 3 5 ]
[ 1 2 3 ]
[ 1 2 4 5 ]
[ 1 2 4 ]
[ 1 2 5 ]
[ 1 2 ]
[ 1 3 4 5 ]
[ 1 3 4 ]
[ 1 3 5 ]
[ 1 3 ]
[ 1 4 5 ]
[ 1 4 ]
[ 1 5 ]
[ 1 ]
[ 2 3 4 5 ]
[ 2 3 4 ]
[ 2 3 5 ]
[ 2 3 ]
[ 2 4 5 ]
[ 2 4 ]
[ 2 5 ]
[ 2 ]
[ 3 4 5 ]
[ 3 4 ]
[ 3 5 ]
[ 3 ]
[ 4 5 ]
[ 4 ]
[ 5 ]

复杂度分析：显然，一次递归调用会产生另外两次递归调用。考虑到这一点，时间复杂度为 (2N)。此外，打印每个子集需要 O(N) 的时间。因此，程序的总时间复杂度为 O(N x 2N)。二维数组列表存储所有子集，子集总数为 O(2N)，而一个子集的最大大小可以为 O(N)。因此，该程序空间复杂度为 O(N x 2N)，其中输入列表中存在的元素总数为 N。

实现：使用位掩码

查找所有子集的突出技术之一是使用位掩码。在这种方法中，我们将输入列表的每个元素视为其对应的位。如果该位被设置，那么我们将该元素包含在当前子集中；否则，则不包含。考虑一个包含三个元素的数组。

Int arr[] = {4, 5, 9}。由于有三个元素，我们将使用三位。对于三位，有 8 (2^3 = 8) 种不同的可能性：000、001、010、011、100、101、110、111。如果从左到右考虑这些可能性，则第一种可能性 (000) 不包含任何元素。第二种可能性 001 仅包含第三个元素 (arr[2])。第三种可能性 010 包含第二个元素 (arr[1])。第四种可能性 011 包含第二个和第三个元素 (arr[1] 和 arr[2])。第五种可能性 100 包含第一个元素 (arr[0])，依此类推。因此，

由于我们不考虑任何空集，因此我们得到的子集是

[9]、[5]、[5, 9]、[4]、[4, 9]、[4, 5]、[4, 5, 9]，这是输入数组 [4, 5, 9] 的要求答案。现在让我们看看涉及的步骤。

步骤 1：声明一个二维列表 answer，用于存放所有子集。

步骤 2：开始一个 for 循环，让 val 从 1 到 2^N -1。

步骤 3：同时，开始一个内部 for 循环，从 0 到 N - 1。

步骤 4：如果 val 中的第 i 位设置为 1，则将输入数组的第 i 个元素添加到当前子集中。

步骤 5：将每个生成的子集添加到二维列表 answer 中。

步骤 6：最后，通过换行符对二维列表 answer 中的每个列表进行排序并显示。

现在让我们看看上述步骤的实现。

文件名： SubsetIntArr1.java

输出

For the array list: [1, 2, 3] 

The subsets are: 
[ 1 ]
[ 2 ]
[ 1 2 ]
[ 3 ]
[ 1 3 ]
[ 2 3 ]
[ 1 2 3 ]

For the array list: [1, 2, 3, 4, 5] 

The subsets are: 
[ 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 ]

复杂度分析：该程序的时间复杂度和空间复杂度与前一个程序相同。