算法:求一个集合的所有子集

2014-07-30 • 技术文章评论

输入有限个数字(可能有重),求其所有的子集。

对于这个问题,暴力穷举无论是伪代码还是实际代码并不好写。对于全集的子集而言,也就只有两个可能,在这个子集中,每个元素只有存在或是不存在两种可能,所以适合用位来解决它,代码好写,省空间还省运算量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
 
public class A {
 
    public static Set<Integer> rs = new HashSet<Integer>();
    public static Map<Integer, Integer> map;
    public static int tmp;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        map = new HashMap<Integer, Integer>();
        Set<Integer> set = new HashSet<Integer>();
 
        while(sc.hasNextInt()) {
            tmp = sc.nextInt();
            if(!set.contains(tmp))
                set.add(tmp);
        }
 
        tmp = 0;
        for(Integer num : set) {
            map.put(tmp++, num);
        }
 
        System.out.println(rs);
        tmp = 1 << tmp;
        for(int i = 1; i < tmp; ++i)
            printSet(i);
    }
 
    public static void printSet(int i) {
        rs.clear();
        char[] bs = Integer.toBinaryString(i).toCharArray();
        for(int e = bs.length - 1; e >= 0; --e) {
            if(bs[e] == '1') {
                rs.add(map.get(bs.length - e - 1));
            }
        }
        System.out.println(rs);
    }
 
}