package com.fishercoder.solutions;


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

/**90. Subsets II
 *
 *Given a collection of integers that might contain duplicates, nums, return all possible subsets.
 Note: The solution set must not contain duplicate subsets.

 For example,
 If nums = [1,2,2], a solution is:
 [
 [2],
 [1],
 [1,2,2],
 [2,2],
 [1,2],
 []
 ]
 */
public class _90 {

    public static class IterativeSolution {
        public static List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList();
            List<Integer> empty = new ArrayList();
            result.add(empty);
            if (nums == null) {
                return result;
            }
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                Set<List<Integer>> temp = new HashSet();
                for (List<Integer> list : result) {
                    List<Integer> newList = new ArrayList(list);
                    newList.add(nums[i]);
                    temp.add(newList);
                }
                result.addAll(temp);
            }
            Set<List<Integer>> resultSet = new HashSet();
            resultSet.addAll(result);
            result.clear();
            result.addAll(resultSet);
            return result;
        }
    }
    
    public static class BacktrackingSolution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList();
            Arrays.sort(nums);
            backtrack(nums, 0, new ArrayList(), result);
            return result;
        }

        void backtrack(int[] nums, int start, List<Integer> curr, List<List<Integer>> result) {
            result.add(new ArrayList(curr));
            for (int i = start; i < nums.length; i++) {
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                curr.add(nums[i]);
                backtrack(nums, i + 1, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }

}

@@ -29,17 +29,16 @@
 tions;%0A%0A
-%0A
 import j
@@ -484,25 +484,16 @@
 ass 
-Iterative
 Solution
  %7B%0A 
@@ -480,32 +480,33 @@
 c class Solution
+1
  %7B%0A        publi
@@ -1425,28 +1425,16 @@
 ass 
-Backtracking
 Solution
  %7B%0A 
@@ -1429,16 +1429,17 @@
 Solution
+2
  %7B%0A     
@@ -2151,10 +2151,853 @@
 %0A    %7D%0A%0A
+    public static class Solution3 %7B%0A        public List%3CList%3CInteger%3E%3E subsetsWithDup(int%5B%5D nums) %7B%0A            List%3CList%3CInteger%3E%3E result = new ArrayList%3C%3E();%0A            List%3CInteger%3E list = new ArrayList%3C%3E();%0A            result.add(list);%0A            Arrays.sort(nums);%0A            backtracking(nums, 0, result, list);%0A            return result;%0A        %7D%0A%0A        private void backtracking(int%5B%5D nums, int start, List%3CList%3CInteger%3E%3E result, List%3CInteger%3E list) %7B%0A            for (int i = start; i %3C nums.length; i++) %7B%0A                if (i %3E start && nums%5Bi%5D == nums%5Bi-1%5D) %7B%0A                    continue;%0A                %7D%0A                list.add(nums%5Bi%5D);%0A                result.add(new ArrayList%3C%3E(list));%0A                backtracking(nums, i+1, result, list);%0A                list.remove(list.size()-1);%0A            %7D%0A        %7D%0A    %7D%0A
 %7D%0A

refactor 90