Java获取数组中的所有子集，并返回List

日常

starorbb · 2022-10-16 · 浏览： 1151

标签： list 集合子集 int array

例子：
> 输入: 
S = {a, b, c, d}
输出:
{a} , {b}, {c}, {d}, {a,b}, {a,c},
{a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, 
{a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}

任何给定集合的子集总数等于2^n（n=集合中的元素数）。如果我们仔细观察，上方例子具有的子集总数为2^4=16（包含空子集），它只不过是从0到15的二进制数，如下所示：
> 0000 {}
0001 {a}
0010 {b}
0011 {a, b}
0100 {c}
0101 {a, c}
0110 {b, c}
0111 {a, b, c}
1000 {d}
1001 {a, d}
1010 {b, d}
1011 {a, b, d}
1100 {c, d}
1101 {a, c, d}
1110 {b, c, d}
1111 {a, b, c, d}

从最右边开始，第i个位置的1表示集合的第i个元素存在，而0表示元素不存在。因此，我们要做的只是生成从0到2^n –1（上述例子为2^4-1=15）的二进制数，其中n是集合的长度。
此方式使用了位运算的方式，以二进制数来表示元素的存在与否。该算法时间复杂度：O(n*(2^n))，外部循环  O(2^n)，内部循环 O(n)。

算法代码（使用泛型）：
```java
    public static <E> List<List<E>> getSubsets(E[] array) {
        int n = array.length;
        List<List<E>> list = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            List<E> temp = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    temp.add(array[j]);
                }
            }
            if (temp.size() != 0) {
                list.add(temp);
            }
        }
        return list;
    }
```

算法代码（仅整型数组）：
```java
    public static List<List<Integer>> getSubsets(int[] array) {
        int n = array.length;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    temp.add(array[j]);
                }
            }
            if (temp.size() != 0) {
                list.add(temp);
            }
        }
        return list;
    }
```

通过主类调用方法并输出全部子集（不包含空子集）：
```java
public static void main(String[] args) {
        List<List<Integer>> list = getSubsets(new int[] {2, 6, 8, 1});
        for (List<Integer> l : list) {
            System.out.print("{ ");
            for (int i : l) {
                System.out.print(i + " ");
            }
            System.out.println("}");
        }
    }
```

#### 回顾Java位运算符：
| 运算符  |  描述 |  例子 | 等同于  |  结果 | 十进制  |
| :------------: | :------------: | :------------: | :------------: | :------------: | :------------: |
| &  | AND - 如果两个位都为 1，则将每个位设置为 1  |  5 & 1 |  0101 & 0001 | 0001  | 1  |
|  丨 | OR - 如果两个位中的任何一个为 1，则将每个位设置为 1  | 5丨1  | 0101丨0001  | 0101  | 5  |
|  ~ | NOT - 反转所有位  | ~5  | ~0101  | 1010  | 5  |
|  ^ |  XOR - 如果两个位中只有一个为 1，则将每个位设置为 1 |  5^1 | 0101^0001  |  0100 | 4  |
|  << | Zero-fill left shift - 通过从右侧推入零并让最左边的位脱落来向左移动  |9 << 1   | 1001 << 1  | 0010  |  2 |
| >>  | Signed right shift - 通过从左侧推入最左侧位的副本并让最右侧位脱落来右移  |  9 >> 1 | 1001 >> 1  | 1100  |  12 |
|  >>> | Zero-fill right shift - 通过从左边推入零并让最右边的位脱落来右移  |  9 >>> 1 | 1001 >>> 1  | 0100  |  4 |

参考内容：[w3schools](https://www.w3schools.cn/java/java_operators.asp "w3schools")  [geeksforgeeks](https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/ "geeksforgeeks")

学后余生

Java获取数组中的所有子集，并返回List