1  /**
 2       * Given a set of distinct integers, S, return all possible subsets.
 3       * 这道题的做法应该要记住！！！！！
 4       * @param s
 5       * @return
 6       */
 7      public ArrayList<ArrayList<Integer>> subsets(int[] s){
 8          ArrayList<ArrayList<Integer>> r = new  ArrayList<ArrayList<Integer>>();
 9          Arrays.sort(s);
10          ArrayList<Integer> sub = new ArrayList<Integer>();
11          r.add(sub);
12          for(int e : s){
13              int cur_size = r.size();
14              for(int j=0;j<cur_size;j++){
15                  sub = new ArrayList<Integer>();
16                  sub.addAll(r.get(j));
17                  sub.add(e);
18                  r.add(sub);
19              }
20          }
21          return r;
22      }
23      /**
24       * Given a collection of integers that might contain duplicates, S, return all possible subsets.
25       * @param num
26       * @return
27       */
28      public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
29          ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
30          Arrays.sort(num);
31          int last = Integer.MAX_VALUE;
32          int mark = 0;
33          ArrayList<Integer> sub = new ArrayList<Integer>();
34          r.add(sub);
35          for(int e:num){
36              int cur_size = r.size();
37              int begin = e==last? mark:0;
38              for(int i = begin;i<cur_size;i++){
39                  sub = new ArrayList<Integer>();
40                  sub.addAll(r.get(i));
41                  sub.add(e);
42                  r.add(sub);
43              }
44              last = e;
45              mark = cur_size;
46          }
47          return r;
48      }