求子集
递归调用法
java源码
import java.util.HashSet;
import java.util.Set;
public class ZiJi {
public static Set<Set<Integer>> ziJi(int []a,int k){
Set<Set<Integer>> newSet=new HashSet<Set<Integer>>();
if(k==0){//第一个元素，加或不加两种情况
//不加
Set<Integer> temp=new HashSet<Integer>();
//加
Set<Integer> temp2=new HashSet<Integer>();
temp2.add(a[0]);
//将两种情况加入集合
newSet.add(temp);
newSet.add(temp2);
return newSet;
}
//获取上层元素集合
Set<Set<Integer>> oldSet=ziJi(a,k-1);
for(Set<Integer> i:oldSet){//对上层的每个元素
//不加元素分支
newSet.add(i);
//加元素分支
Set<Integer> temp=new HashSet<Integer>();
temp.addAll(i);
temp.add(a[k]);
newSet.add(temp);
}
return newSet;
}
public static void main(String[] args) {
int []a={1,2,3};
Set<Set<Integer>> s=ziJi(a,a.length-1);
System.out.println(s);
}
}
运行结果
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
巧用二进制法
核心思想：对于一个含有N个元素的集合的子集个数可以计算得到共有
2
N
2^N
2N个 所以用（0——
2
N
2^N
2N-1）的2进制来表示对N个元素的选与不选（0表示不选，1表示选） 如：对于3个元素的集合，1 写成二进制 001——表示就是前两个不选，最后一个选。
java源码：
public static void main(String[] args) {
char []a={'a','b','c'};
for(int i=0;i<Math.pow(2, a.length);i++){
int temp=i;
for(int j=0;j<a.length;j++){
if((temp&1)==1){
System.out.print(a[j]);
}
temp=temp>>1;
}
System.out.println();
}
}
运行结果
a
b
ab
c
ac
bc
abc
