如何获取ArrayList子集？修正生成1到N整数幂集的代码问题

你的代码问题根源 #

你当前的代码只创建了一个HashSet<Integer>实例，随后循环将这个实例重复添加到结果列表中。由于Java中集合是引用类型，列表里的所有元素都指向同一个集合对象，最终输出自然全是完整的{0,1,2,3}。

关于集合复制的问题 #

可以复制集合来生成独立的子集，但HashSet没有类似Arrays.copyOfRange的直接方法。你可以通过new HashSet<>(原集合)创建一个全新的集合副本，每个副本都是独立对象，不会互相干扰。不过直接复制完整集合再删减并不是生成幂集的高效方式，更合理的是逐个构建每个子集。

正确实现方法 #

方法一：二进制位掩码法

利用整数的二进制位表示元素是否存在，每一位对应1-N中的一个元素，配合位运算快速生成所有子集：

import java.util.ArrayList;
import java.util.HashSet;

public class HW3 {
    public static void main(String[] args) {
        System.out.println(powerset(3));
    }

    public static ArrayList<HashSet<Integer>> powerset(int N) {
        ArrayList<HashSet<Integer>> result = new ArrayList<>();
        // 添加题目要求的[0]子集
        result.add(new HashSet<>(){{ add(0); }});

        // 生成1到N的所有子集，共2^N个
        int totalSubsets = (int) Math.pow(2, N);
        for (int i = 1; i < totalSubsets; i++) {
            HashSet<Integer> subset = new HashSet<>();
            for (int j = 1; j <= N; j++) {
                // 检查第j-1位是否为1，为1则加入对应元素
                if ((i & (1 << (j-1))) != 0) {
                    subset.add(j);
                }
            }
            result.add(subset);
        }
        return result;
    }
}

说明：每个整数i的二进制位对应是否包含1-N的元素，比如i=3（二进制011）对应子集{1,2}，循环遍历所有可能的整数即可生成全部子集，再加上初始的{0}就完全匹配题目预期输出。

方法二：迭代构建法

从初始子集出发，逐个添加元素并扩展现有子集，逐步构建完整幂集：

import java.util.ArrayList;
import java.util.HashSet;

public class HW3 {
    public static void main(String[] args) {
        System.out.println(powerset(3));
    }

    public static ArrayList<HashSet<Integer>> powerset(int N) {
        ArrayList<HashSet<Integer>> result = new ArrayList<>();
        // 初始添加[0]子集
        result.add(new HashSet<>(){{ add(0); }});

        // 逐个处理1到N的元素
        for (int num = 1; num <= N; num++) {
            int currentSize = result.size();
            // 复制现有子集（排除[0]）并添加当前元素，生成新子集
            for (int i = 1; i < currentSize; i++) {
                HashSet<Integer> newSubset = new HashSet<>(result.get(i));
                newSubset.add(num);
                result.add(newSubset);
            }
            // 添加仅包含当前元素的子集
            result.add(new HashSet<>(){{ add(num); }});
        }
        return result;
    }
}

说明：每次处理一个元素时，将现有所有子集（除了{0}）复制并添加当前元素，再将新子集加入结果，同时添加单独的当前元素子集，最终生成所有符合要求的组合。

内容的提问来源于stack exchange，提问作者Ezequiel Soler Perez