利用二进制方法求子集

干货分享 / 2022-07-18

前言

做项目的时候遇到需要求子集和的问题,偶然看到使用二进制的方法进行求解,顺手记了下来

原理

由于一个集合的子集数为 2 ^ 集合长度,观察二进制位

假如一个集合为 [1, 2, 3],则子集数量为 2 ^ 3 = 8 个,0 到 7 的二进制数分别为 000,001,010,011,100,101,110,111

集合有三个数,二进制位数也为三,一一对应,当二进制位为 0 时代表不加入集合,为 1 时代表加入集合,故而每一个二进制数代表了一个子集

于是代码就很容易写出来了

代码

java 实现:

public List<Set<Integer>> getCombinations(List<Integer> tagsList) {
    if (tagsList.size() > 0) {
        List<Set<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.pow(2, tagsList.size()); i++) {
            Set<Integer> subResult = new HashSet<>();
            int num = i;
            for (Integer integer : tagsList) {
                if ((num & 1) == 1) { // 枚举 num,看末位与1相与是否为1,若为1则代表二进制末位为1,故将集合中的元素添加入子集
                    subResult.add(integer);
                }
                num >>= 1; // 将 num 的二进制向右移一位,即相当于除以二
            }
            result.add(subResult);
        }
        return result;
    } else {
        return null;
    }
}

总结

还有很多巧妙的解法需要学习啊