前言
做项目的时候遇到需要求子集和的问题,偶然看到使用二进制的方法进行求解,顺手记了下来
原理
由于一个集合的子集数为 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;
}
}
总结
还有很多巧妙的解法需要学习啊