这道题的做法，一定得掌握啊！！！ elegant & beautiful & concise
下面是AC代码：
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 }