Given a collection of integers that might contain duplicates,nums, return all possible subsets (the power set).

Note:The solution set must not contain duplicate subsets.

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

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

tag: backtracking

注意结合permutation1/2 和 subset 1/2， 注意recursion和iterative多种解法

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) return ans;

        Arrays.sort(nums);
        //Set<List<Integer>> temp = new HashSet<>();
        dfs(nums, 0, new boolean[nums.length], new ArrayList<>(), ans);

        // for (List<Integer> l : temp){
        //     ans.add(l);
        // }

        return ans;
    }

    private void dfs(int[] nums, int index, boolean[] used, List<Integer> path, List<List<Integer>> temp){

        temp.add(new ArrayList<>(path));

        if (index == nums.length) return;

        int i = index;
        while (i < nums.length){

            path.add(nums[i]);
            dfs(nums, i + 1, used, path, temp);
            path.remove(path.size() - 1);
            i++;
            while (i < nums.length && nums[i] == nums[i - 1]) i++;
        }
    }
}