problem
输入一个集合，输出这个集合的所有子集。
solution
集合A={a,b,c},对于任意一个元素，在每个子集中，要么存在，要么不存在。 映射为子集：
(a,b,c)
111 -> (a,b,c)
110 -> (a,b)
101 -> (a,c)
100 -> (a)
011 -> (b,c)
010 -> (b)
001 -> (c)
000 -> @(@表示空集)
观察以上规律，与计算机中数据存储方式相似，故可以将整数(000~111)与集合映射，通过该整型数逐次增可遍历获取所有的数，即获取集合的相应子集。
Java code
public class Demo {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
//对list进行去重
HashSet<String> hashSet = new HashSet<String>(list);
list.clear();
list.addAll(hashSet);
System.out.println(subset(list));
}
public static List<List<String>> subset(List<String> list){
List<List<String>> result = new ArrayList<>();
int num = list.size() == 0 ? 0 : 1<<list.size(); // int4字节 32个位 有几个元素占几位
List<String> subSet = null;
for (int i = 0; i < num; i++ ) {
subSet= new ArrayList<>();
int index = i;
for(int j = 0; j < list.size(); j++) {
if((index & 1) == 1) { // 判断最低位是否为1
subSet.add(list.get(j));
}
index >>= 1;
}
result.add(subSet);
}
return result;
}
}
/*
output：[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c], [d], [a, d], [b, d], [a, b, d], [c, d], [a, c, d], [b, c, d], [a, b, c, d]]
*/
Discussion
不要用右移运算，右移存在符号位填充，某些情况下会出现死循环。详见《剑指offer》2.4.5节
int index = i;
for(int j = 0; j < list.size(); j++) {
if((index & 1) == 1) { // 判断最低位是否为1
subSet.add(list.get(j));
}
index >>= 1; // 右移一位
}