Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
和subsets 算法一致，不过在加入到result前 先判定是否在hashmap中。

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         Arrays.sort(S);
 6         HashMap<ArrayList<Integer>, Integer> hm = new HashMap<ArrayList<Integer>, Integer>();
 7         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 8         for(int i = 0; i < (1 << S.length); i ++){
 9             ArrayList<Integer> row = new ArrayList<Integer>();
10             for(int j = 0; j < S.length; j ++){
11                 if((i & (1 << j)) != 0) row.add(S[j]);
12             }
13             if(!hm.containsKey(row)){
14                 hm.put(row, 1);
15                 result.add(row);
16             }
17         }
18         return result;
19     }
20 }

第三遍：

使用recursive 做：

 1 public class Solution {
 2     ArrayList<List<Integer>> result = null;
 3     public List<List<Integer>> subsetsWithDup(int[] num) {
 4         result = new ArrayList<List<Integer>> ();
 5         if(num == null || num.length == 0) return result;
 6         Arrays.sort(num);
 7         result.add(new ArrayList<Integer>());
 8         subset(num, 0, new ArrayList<Integer>());
 9         return result;
10     }
11     public void subset(int[] num, int pos, ArrayList<Integer> row){
12         int pre = Integer.MIN_VALUE;
13         for(int i = pos; i < num.length; i ++){
14             if(num[i] != pre){
15                 pre = num[i];
16                 ArrayList<Integer> nrow = new ArrayList<Integer> (row);
17                 nrow.add(pre);
18                 result.add(nrow);
19                 subset(num, i + 1, nrow);
20             }
21         }
22     }
23 }