Leetcode: 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],
  []
]

第二遍Better做法：

第11行 i>start && nums[i]==nums[i-1] 就skip很不错

 1 public List<List<Integer>> subsetsWithDup(int[] nums) {
 2     List<List<Integer>> list = new ArrayList<>();
 3     Arrays.sort(nums);
 4     backtrack(list, new ArrayList<>(), nums, 0);
 5     return list;
 6 }
 7 
 8 private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
 9     list.add(new ArrayList<>(tempList));
10     for(int i = start; i < nums.length; i++){
11         if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
12         tempList.add(nums[i]);
13         backtrack(list, tempList, nums, i + 1);
14         tempList.remove(tempList.size() - 1);
15     }
16 }

第一遍做法：需要已访问数组，当前后元素一样且前面元素并未访问，这个时候就是重复的case, continue,

注意这里的判重复条件跟3Sum那种是不一样的，

3SUM防止重复方法是 if (i<num.length-1 && num[i]==num[i+1]) continue, 即当前starter如果与前一个相同，即跳过。这个做法在3sum可以，在这里不行。 3SUM这样做可以是因为它可以靠2SUM 子函数来确保找到non-duplicate的2set，然后只需要确保starter不一样，即可保证3set也non-duplicate. 然而这道题这里是recursion，如果只判断当前starter与前一个一样就跳过，那么{2,2,3}都没法成为一个feasible set，因为第二个2需要被加入时总是被跳过。

正确做法是需要设置已访问数组，当前后元素一样且前面元素并未访问，这个时候才是重复的case，才被跳过

 1     public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
 2         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 3         ArrayList<Integer> item = new ArrayList<Integer>();
 4         if (num==null || num.length==0) return res;
 5         Arrays.sort(num);
 6         boolean[] visited = new boolean[num.length];
 7         for (int len=0; len<=num.length; len++) {
 8             helper(res, item, num, 0, len, visited);
 9         }
10         return res;
11     }
12     
13     public void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> item, int[] num, int starter, int len, boolean[] visited) {
14         if (item.size() == len) {
15             res.add(new ArrayList<Integer>(item));
16             return;
17         }
18         for (int i=starter; i<num.length; i++) {
19             if (i>0 && num[i]==num[i-1] && !visited[i-1]) continue;
20             item.add(num[i]);
21             visited[i] = true;
22             helper(res, item, num, i+1, len, visited);
23             item.remove(item.size()-1);
24             visited[i] = false;
25         }
26     }