利用二进制方法求子集

前言

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

原理

由于一个集合的子集数为 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;
    }
}

总结

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