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 Solution1 {
        public 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 Solution2 {
        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);
            }
        }
    }

    public static class Solution3 {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            result.add(list);
            Arrays.sort(nums);
            backtracking(nums, 0, result, list);
            return result;
        }

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

@@ -158,294 +158,8 @@
 t;%0A%0A
-/**%0A * 90. Subsets II%0A *%0A *Given a collection of integers that might contain duplicates, nums, return all possible subsets.%0A Note: The solution set must not contain duplicate subsets.%0A%0A For example,%0A If nums = %5B1,2,2%5D, a solution is:%0A %5B%0A %5B2%5D,%0A %5B1%5D,%0A %5B1,2,2%5D,%0A %5B2,2%5D,%0A %5B1,2%5D,%0A %5B%5D%0A %5D%0A */%0A
 publ

refactor 90