package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/subsets-ii/
 */
public class Problem90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        Arrays.sort(nums);
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }
        set.add(numList);
        subsets(nums, set);
        for (List<Integer> list : set) {
            result.add(list);
        }
        return result;
    }

    private void subsets(int[] nums, Set<List<Integer>> result) {
        if (nums.length == 0) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = new ArrayList<>();
            int[] newArray = new int[nums.length - 1];
            int idx = 0;
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                newArray[idx++] = nums[j];
                list.add(nums[j]);
            }
            if (result.add(list)) {
                subsets(newArray, result);
            }
        }
    }
}

@@ -57,21 +57,26 @@
 va.util.
-Array
+Collection
 s;%0Aimpor
@@ -284,64 +284,8 @@
 ) %7B%0A
-        List%3CList%3CInteger%3E%3E result = new ArrayList%3C%3E();%0A
     
@@ -310,16 +310,17 @@
 er%3E%3E set
+s
  = new H
@@ -343,305 +343,94 @@
     
-Arrays.sort(nums);%0A        List%3CInteger%3E numList = new ArrayList%3C%3E();%0A        for (int num : nums) %7B%0A            numList.add(num);%0A        %7D%0A        set.add(numList);%0A        subsets(nums, set);%0A        for (List%3CInteger%3E list : set) %7B%0A            result.add(list);%0A        %7D%0A        return result
+subsetsWithDup(nums, 0, new ArrayList%3C%3E(), sets);%0A        return new ArrayList%3C%3E(sets)
 ;%0A  
@@ -446,16 +446,23 @@
 private 
+static 
 void sub
@@ -465,16 +465,23 @@
  subsets
+WithDup
 (int%5B%5D n
@@ -485,20 +485,27 @@
 %5D nums, 
-Set%3C
+int index, 
 List%3CInt
@@ -513,134 +513,44 @@
 ger%3E
-%3E result) %7B%0A        if (nums.length == 0) %7B%0A            return;%0A        %7D%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A    
+ accu, Set%3CList%3CInteger%3E%3E result) %7B%0A
     
@@ -567,20 +567,19 @@
 nteger%3E 
-list
+tmp
  = new A
@@ -585,24 +585,28 @@
 ArrayList%3C%3E(
+accu
 );%0A         
@@ -608,78 +608,54 @@
     
-    int%5B%5D newArray = new int%5Bnums.length - 1%5D;%0A            int idx = 0
+Collections.sort(tmp);%0A        result.add(tmp)
 ;%0A  
@@ -660,20 +660,16 @@
         
-    
 for (int
@@ -673,16 +673,20 @@
 int 
-j = 0; j
+i = index; i
  %3C n
@@ -697,17 +697,17 @@
 length; 
-j
+i
 ++) %7B%0A  
@@ -720,115 +720,25 @@
     
-    if (i == j) %7B%0A                    continue;%0A                %7D%0A                newArray%5Bidx++%5D = 
+accu.add(
 nums%5B
-j%5D
+i%5D)
 ;%0A  
@@ -751,137 +751,92 @@
     
-    list.add(nums%5Bj%5D);%0A            %7D%0A            if (result.add(list)) %7B%0A                subsets(newArray, result);%0A            %7D
+subsetsWithDup(nums, i + 1, accu, result);%0A            accu.remove(accu.size() - 1);
 %0A   

Solve problem 90